CODEWITHSUNDEEP
algorithmgraph
Artur
Artur

Reputation: 591

Graph Theory: Queries with bounded edge weight in undirected graph

Given a weighted undirected graph of n <= 200000 nodes and m <= 200000 edges. Edge weights (integers) can be upto 1e9. There are q <= 200000 queries. Each query gives two nodes u v and a integer bound p (<= 1e9). If there's a path between u and v such that each edge weight in the path is <= p then answer is yes else no.

Notice that the path doesn't have to shortest. Just the maximum weight on the path is <= p. Naive approaches of course don't work. How to answer the queries fast (in O(n lg n) or something like that)?

Upvotes: 1

Views: 430

Answers (2)

Foyaz Akanda
Foyaz Akanda

Reputation: 1

  1. First build the minimum spanning tree from the given graph.
  2. Then you can use heavy light decomposition technique to answer each query in logn.

So overall complexity of O(mlogm + qlogn). You can find about heavy light decomposition in the following link https://blog.anudeep2011.com/heavy-light-decomposition/

Upvotes: 0

coder
coder

Reputation: 12982

The problem that you describe is known as: Widest Path Problem and you can find it here: https://en.wikipedia.org/wiki/Widest_path_problem .
It could be easily proved that a path between u,v with the minimum maximum cost for each u,v is equal to the minimum spanning tree.So you need to find the minimum spanning tree in order to be sure that you have minimized the maximum cost in each path between two vertices u,v.
The difficult part is to decide for each query if the path from u to v has maximum cost less or equal than p.

  • The best approach would be using cartesian trees (described in the wikipedia linked) which will allow you to answer each query in constant time and I think building the cartesian tree would be O(nlogn) so overall O(nlogn + q).But this approach is difficult to implement.

  • I think what you're looking for is to use lowest common ancestor algorithm to answer in logn every query ,after you find the minimum spanning tree.So find minimum spanning tree (O(E log E)) and use lowest common ancestor with some preprocessing to be able to answer each query in O(log n) so overall O( qlogn + ElogE). A very good approach to the Lowest Common Ancestor and the preprocessing could be found here: https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/ The article above describes very well all the solutions and gives enough help code useful to your problem.

Upvotes: 0

Related Questions