Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 577
datcn Avatar asked Mar 23 '12 02:03

datcn


1 Answers

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: vin and vout.
  2. For each node v, add an edge of capacity one from vin to vout.
  3. Replace each other edge (u, v) in the graph with an edge from uout to vin of capacity 1.
  4. Add in a new dedicated destination node t.
  5. For each of the target nodes v, add an edge from vin to t with capacity 1.
  6. Find a max-flow from sout 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 vin to vout, 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!

like image 180
templatetypedef Avatar answered Sep 27 '22 17:09

templatetypedef