# Finding a pair of edge disjoint paths in a graph, such that the lengths of each one of the paths is smaller than a given constant

I know how to find a pair of disjoint paths with the minimum sum of lengths (Suurballe's algorithm). I also have a formulation of an integer linear program that solves the following problem, which generalizes my problem: Given two vertices u and v in a graph G, out of all of the disjoint pairs of paths connecting u and v in G, find a pair with the minimal length of the longer path in the pair. (Of course, this problem may be reformulated for groups of more than two disjoint paths).

Does anyone have an idea for an efficient (polynomial?) algorithm for solving any of these problems (The problem in the title or the generalized problem?)

Thanks!

-
Migrate to cs.SE? –  Realz Slaw Nov 17 '13 at 4:47
I think that this problem was found to be NP hard.. You can do it if you want.. –  Yoav Bar Sinai Nov 19 '13 at 15:32