Find a vertex disjoint path from source to destination
algorithm, graph-theory, np
Solution
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.
Problem
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: