Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
Cross-posted to Stackoverflow and thebirdietoldme.com (Please don't do this.) –  Douglas S. Stones Dec 4 '12 at 3:16
add comment

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.