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).