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

algorithmsgraph theorynp-complete

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.

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

Related Question