Search code examples
algorithmgraph-theorynp

Find a vertex disjoint path from source to destination

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:

enter image description here

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.