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

Question

Given a 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 the graph G, with a constraint that the sum of paths length is not greater than a predefined value T.

Answer 1

You can start with transforming a vertex-disjoint paths problem to edge-disjoint paths problem. See this answer to other question for details.

Now you can solve Minimum-cost flow problem on this graph to find any number of disjoint paths having minimal sum of path lengths. Do do this, assign flow capacity for each edge equal to 1, then search for a minimum-cost flow between s and t with flow equal to the needed number of paths.

To find the maximum number of paths, apply minimum-cost flow procedure on each step of binary search, starting from some initial number of paths, which may be determined by one of the following procedures:

1. If you expect the maximum number of paths to be large, solve Maximum flow problem for this graph.
2. If you expect the maximum number of paths to be small, use one-sided binary search (also with minimum-cost flow procedure on each step).

Answer 2

Since you are only interested in the number of vertex-disjoint paths you can use Menger's theorem (for proof look here) that states as follows:

Let G be a finite undirected graph and x and y two nonadjacent vertices. Then the theorem states that the size of the minimum vertex cut for x and y (the minimum number of vertices whose removal disconnects x and y) is equal to the maximum number of pairwise vertex-independent paths from x to y.

But this doesn't satisfy the constraint that the sum of paths length is not greater than a predefined value T.

For that you'll have to use a version of of Menger's theorem for paths of bounded length that is presented here: http://www.math.elte.hu/~lovasz/scans/mengerian.pdf