[Solved]: Non intersecting paths in a graph

Problem Detail: 

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.

Asked By : Ron Teller

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19413