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

问题:

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?

回答1:

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!