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.

Improve this question
$\endgroup$
7
  • 7
    $\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
    Commented Nov 7, 2011 at 11:04
  • 3
    $\begingroup$ This smells like homework. $\endgroup$
    – Jeffε
    Commented Nov 7, 2011 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$
    – Josephine Moeller
    Commented Nov 7, 2011 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
    Commented Nov 7, 2011 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
    Commented Nov 8, 2011 at 6:53

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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