Find a vertex disjoint path from source to destination

Question

Is there a deterministic algorithm to check if a graph contains a vertex-disjoint path from a source to destination, with complexity O(nm^2) (n is number of vertices, m is number of edges) or is this NP-Hard (if so, why)? Vertex disjoint path means a path with no common internal vertex. eg.

s -> a -> b -> c -> d  
s -> x -> y -> z -> d

Are vertex disjoint but

s -> a -> b -> c -> d
s -> x -> a -> z -> d
          ^

Are not since a is common vertex.

---

The full question is:

Answer 1

The problem (asked in the question, find "ONE" vertex disjoint path between s and t which is different from the picture of the question posted) is not NP-hard and can be solved in polynomial time O(V^2E). Moreover, the question of is there are k disjoint paths between s and t is also not NP-Complete.

The article which was referred above to prove NP-completeness (http://www.shannarasite.org/kb/kbse48.html) has a subtle difference....there you do not know s and t, thus the problem becomes hard. But, once you fix s and t, it is polynomial.

Here is the algorithm to find a vertex disjoint path in polynomial time ---

Convert this problem to a maximum flow problem and use Dinic's algorithm to solve it in O(V^2E) http://en.wikipedia.org/wiki/Dinitz_blocking_flow_algorithm

This is the conversion:

Pick the source s and destination t vertices between which you want to find the disjoint path. For each vertex v add two new vertices to G' (the graph we are constructing) , i.e. for each v \in G add v_1 and v_2 to G'.

For each edge (a,b) add the following edges (a_1, a_2), (b_1, b_2), (a_2, b_1) and (b_2, a_1) (remember that the vertices have already been transformed, and note the direction of the edges).

Add S and T to G' and edges (S,s_1), and (t_2, T).

Assign weight of 1 to all the edges and run the max-flow algorithm (between S and T). If you get a max-flow of 1, then that flow (or path) corresponds to the vertex disjoint path in your original graph.

Now to kind k disjoint paths :

Assign weight of k for edges (S,s_1), (t_2, T) , (s1_, s_2), and (t_1, t_2).....and weight 1 for the remaining edges...run the Dinic's algo again, and if there is max flow of capacity k, that gives you the disjoint paths.

Answer 2

The problem is NP-Hard. This may be proven by reduction from 3-SAT. Here is sketch of a proof.

Assign 'n' source/destination pairs (for each variable). Connect each pair with two paths, each having 'm' internal nodes (for 'm' clauses). One path is for the case when variable is 'true', other one - 'false'.

Also assign 'm' source/destination pairs (for each clause). Connect each pair with 3 paths, each path - through corresponding internal node of "variable" paths, choosing 'true' or 'false' paths if this variable is negated or not in the clause.

Then find 'm+n' vertex-disjoint paths to solve 3-SAT.