2
$\begingroup$

I'm trying to come up with a good algorithm for the following decision problem:

Let $G=(V,A)$ be a directed graph and let $s,t \in V$. Are there at-least 2 non-intersecting paths from $s$ to $t$?

By non-intersecting I mean that if $P_1$ and $P_2$ are non-intersecting paths from $s$ to $t$ then $\forall e\in P_1\in A, e\notin P_2$ (can share vertices but not edges).

I thought of the following algorithm:

  1. Find the shortest path $P\in A$ in $G$ from $s$ to $t$. if no such path exist, return false;
  2. Find the shortest path $P'\in A-P$ in $G$ from $s$ to $t$. if no such path exists, return false; else return true.

I didn't find a contradicting example but so far I was unable to prove its correctness.

Ideas about proof approaches for this algorithm or suggesting other algorithms is welcome.

$\endgroup$
  • $\begingroup$ Is your graph weighted or unweighted? Unweighted, I presume? $\endgroup$ – D.W. Dec 31 '13 at 16:51
3
$\begingroup$

Nope, this algorithm doesn't work. It is possible to find an explicit counterexample. Since it sounds like this is an exercise you're doing to learn algorithms, I won't spoil the exercise for you, but I'll just give you some hints that may help you find a counter example.

  • Start with a graph containing just a single path from $s$ to $t$, and nothing else. Make it a fairly short path, say, 5 edges long.

  • Introduce a long path from $s$ to $t$ (say, 10 edges long or so) that coincides with the short path for a brief while then diverges.

  • Now introduce a second long path from $s$ to $t$ with two properties: (a) it is edge-disjoint with the first long path, (b) it has at least one edge in common with the short path.

Finding a counterexample is a little tricky, but draw it out and try some ideas, and I bet you'll be able to figure out.


Your approach doesn't work, but there are other algorithms to solve this problem. However, they're fairly complicated: more complicated than your could reasonably be expected to discover on your own. Assuming this is a homework/exercise, I can't just can't believe your teacher would assign you an exercise that requires you to independently re-discover those algorithms -- so there must be some other trick or background information available to you. You might check in with your teacher.

The other algorithms use the following idea: Look for a "funnel" edge $e$ such that all paths from $s$ to $t$ "funnel through" the edge $e$ (i.e., all paths from $s$ to $t$ must include the edge $e$). If you find such an edge, obviously there is no pair of edge-disjoint paths from $s$ to $t$. If you don't find such an edge, then it turns out that there's guaranteed to exist two edge-disjoint paths from $s$ to $t$. Proving this is tricky, though, as is devising an efficient algorithm to rapidly test for the existence of such an edge.


Since you asked for references, this problem is solved by the following characterization: there are two vertex-disjoint paths from $s$ and $t$ if and only if $s,t$ are part of the same biconnected component. There are fancy algorithms to decompose a graph into biconnected components in linear time. Similarly, there are two edge-disjoint paths from $s$ and $t$ if and only if $s,t$ are part of the same 2-edge-connected component. There are fancy algorithms to decompose a graph into 2-edge-connected components in linear time (or, you can reduce to the problem of computing biconnected components by computing a new graph that swaps vertices and edges).

So, an efficient answer to your question is: decompose the graph into 2-edge-connected components (using the algorithms mentioned in the previous paragraph), then test whether $s$ and $t$ are in the same component.

For more, see e.g., https://en.wikipedia.org/wiki/Biconnected_component and https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29 and https://en.wikipedia.org/wiki/K-edge-connected_graph.

$\endgroup$
  • $\begingroup$ Actually it's not an exercise, I was reading some article that made me think about this problem (It's not mentioned, I thought about it myself). Anyway thanks for the help- if you have any relevant references to share i'd like to read them. $\endgroup$ – Ron Teller Jan 1 '14 at 7:07
  • $\begingroup$ @RonTeller, cool, I've edited my answer to add references to the standard algorithms for this problem. Be warned, they are not simple -- but they are efficient. $\endgroup$ – D.W. Jan 1 '14 at 16:42
  • $\begingroup$ As a counterexample pick the graph with nodes A,B,C,D and edges (in the format (start,end,length) ) A,B,1 A,C,3 B,C,1 B,D,3 C,D,1. There are two disjoint paths from A to D, namely ABD of length 4 and ACD of length 4, the shortest path is however A,B,C,D of length 3: if you remove edges AB BC and CD your graph is not connected anymore. An unweighted counterexample can be made by adding nodes E F G Hreplacing edges AC with AE EF FC and BD with BG GH HD $\endgroup$ – pqnet Aug 31 '14 at 21:21

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.