3
$\begingroup$

Given an undirected sparse graph G and a list of queries (each query consisting of two nodes), how to determine if there exists exactly one simple path between them (for each query) ? I have a (trivial) solution based on a breadth-first search (for each query the complexity would be O(V+E)) but is there a more efficient way to answer the queries?

You don't have to find the actual simple path, just answer each query with a True/False answer.

This question was asked as part of the Latin American regional competition of the 2011 ACM International Collegiate Programming Contest.

$\endgroup$
  • 6
    $\begingroup$ It might help to compute the decomposition of your graph into biconnected components ( en.wikipedia.org/wiki/Biconnected_component ) in linear time. If you have a query where the two vertices come from the same biconnected component (and this has > 2 vertices), then there are at least two simple paths (by definition). If the query vertices come from different biconnected components, you might speed up your procedure by searching in the block tree instead of in the original graph. Depending on the nr of biconnected components vs vertices, the speedup might be significant. $\endgroup$ – Bart Jansen Nov 7 '11 at 11:04
  • 3
    $\begingroup$ This smells like homework. $\endgroup$ – Jeffε Nov 7 '11 at 11:22
  • $\begingroup$ I agree, it smells homeworky. Since there are so few constraints on the problem, there are a number of obvious options to pursue. $\endgroup$ – John Moeller Nov 7 '11 at 17:11
  • 2
    $\begingroup$ I think that a problem in a programming contest is also off-topic in a similar way that an exercise in a textbook is off-topic. Also please reveal the source from the beginning (although I appreciate that you revealed the source eventually). $\endgroup$ – Tsuyoshi Ito Nov 7 '11 at 20:46
  • 4
    $\begingroup$ @jplot: Please edit the question to include the source; do not assume that people always read all comments. $\endgroup$ – Jukka Suomela Nov 8 '11 at 6:53
14
$\begingroup$

Ok, now that you've revealed the motivation: there is exactly one simple path between two nodes iff there is a path in which every edge is a bridge of the graph. So find all the bridges (standard linear time by depth first search) and compute the connected components of the subgraph they form. Two vertices have a unique simple path iff they belong to the same component.

$\endgroup$
  • 1
    $\begingroup$ Oops; your answer was much simpler and faster than mine! $\endgroup$ – Andrew D. King Nov 8 '11 at 4:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.