Find the maximum number of vertex-disjoint paths in a graph with constraint

Question

Given the undirected graph G = (V, E), each edge is associated with a non-negative value.

How to find the maximum number of vertex-disjoint paths from s to t on a graph G with the restriction that the sum of the path lengths does not exceed a given value T.

Answer 1

You can start by converting a problem with vertices and disjoint paths into a problem with border-disjoint paths. See this answer to another question for more details.

Now you can solve the minimum cost problem on this graph to find any number of disjoint paths that have the minimum amount of path length. Do this, assign the throughput for each edge to 1, then search for the minimum cost stream between s and t with the stream equal to the required number of paths.

To find the maximum number of paths, apply the minimum flow rate procedure at each stage of the binary search, starting with a certain initial number of paths, which can be determined by one of the following procedures:

• If you expect the maximum number of paths to be large, solve the "Maximum Flow Problem" for this graph.
• If you expect the maximum number of paths to be small, use a one-way binary search (also with a minimum flow procedure at each step).

Answer 2

Since you are only interested in the number of vertex-disjoint paths, you can use the Menger theorem (see the proof here ), which states the following:

Let G be a finite undirected graph, and x and y be two non-adjacent vertices. Then the theorem states that the size of the minimum vertex cut for x and y (the minimum number of vertices whose removal is disabled by x and y) is equal to the maximum number of paths from x to y that are not dependent on the vertex.

But this does not satisfy the restriction that the sum of the path lengths does not exceed the predetermined value T.

For this you will have to use the version of Menger’s theorem for paths of limited length which is presented here : http://www.math.elte.hu/~lovasz/scans/mengerian.pdf