How to find all vertex-disjoint paths in a graph?

Question

Suppose there are 3 target nodes in a graph.

A vertex-disjoint path means there is not any same node except the end nodes during the path.

For any one single node, say node i, how to find all vertex-disjoint paths from node i to the three target nodes?

Solution

You can solve this problem by reducing it to a max-flow problem in an appropriately-constructed graph. The idea is as follows:

1. Split each node v in the graph into to nodes: v_in and v_out.
2. For each node v, add an edge of capacity one from v_in to v_out.
3. Replace each other edge (u, v) in the graph with an edge from u_out to v_in of capacity 1.
4. Add in a new dedicated destination node t.
5. For each of the target nodes v, add an edge from v_in to t with capacity 1.
6. Find a max-flow from s_out to t. The value of the flow is the number of node-disjoint paths.

The idea behind this construction is as follows. Any flow path from the start node s to the destination node t must have capacity one, since all edges have capacity one. Since all capacities are integral, there exists an integral max-flow. No two flow paths can pass through the same intermediary node, because in passing through a node in the graph the flow path must cross the edge from v_in to v_out, and the capacity here has been restricted to one. Additionally, this flow path must arrive at t by ending at one of the three special nodes you've identified, then following the edge from that node to t. Thus each flow path represents a node-disjoint path from the source node s to one of the three destination nodes. Accordingly, computing a max-flow here corresponds to finding the maximum number of node-disjoint paths you can take from s to any of the three destinations.

Hope this helps!

Comments

[datcn]

Maybe my expression abt vertex-disjoint is not clear enough. For node s and node t, there is a path s->a-〉b->c->d->t, there are also another path beginning from s like s->e->f->g->h->t. In this case, this is a vertex-disjoint path. But if there is a path as s->e->f->g->d->t, this is not a vertex disjoint.

[razshan]

what would be the running time of this solution? O(nm) ?

[templatetypedef]

@razshan Think of it this way: how much time is spent on preprocessing and how much time is spent on max flow?

[razshan]

hmm preprocessing looks linear in time, but finding the max-flow from s_out to to will take either O(n * m^2) or (n^2 * m) which will drive the big Oh notation. Does this seem logical?

[razshan]

Also for steps 1 and 2, do we have to split the sink node in to t_in and t_out as well?