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

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.

-
Cross-posted to Stackoverflow and thebirdietoldme.com (Please don't do this.) – Douglas S. Stones Dec 4 '12 at 3:16
Just wanted to clarify @DouglasS.Stones thebirdietoldme.com grabs all of the questions/answers in the stack exchange network into one site. It's currently offline, but just wanted to clarify this. – pqsk Sep 1 '14 at 0:39

## 1 Answer

Garey and Johnson, page 214, $K$th Shortest Path:

Given a graph $G=(V,E)$, a positive integer length for each edge, specified vertices $s,t$, and positive integers $B,K$, the question whether there are $K$ or more distinct simple paths from $s$ to $t$ each of length $B$ or less, is not even known to be in NP.

This doesn't quite answer your question, since it does not require the paths to be vertex-disjoint, but it may show you where to start looking.

See also page 217, Maximum Length-Bounded Disjoint Paths: given a graph, two specified vertices, and two positive integers $J,K$, does the graph have $J$ or more mutually vertex-disjoint paths joining the vertices, none involving more than $K$ edges. This one is NP-complete, and actually looks more relevant than the first one.

-