Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Cross-posted to Stackoverflow and (Please don't do this.) – Douglas S. Stones Dec 4 '12 at 3:16
Just wanted to clarify @DouglasS.Stones 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

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|cite|improve this answer

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.