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 (Surballe's algorithm). I also have a formulation of an ILP 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 a开发者_运维技巧n idea for an efficient (polynomial?) algorithm for solving any of these problems (The problem in the title or the generalized problem?)

Thanks!

I think it's an NP problem, because I could reduce knapsack problem to this and according to this article knapsack problem is NP-complete. indeed knapsack problem has a Pseudo-polynomial time algorithm in the value of the knapsack size, but it has no polynomial time algorithm in the size of the input.

reducing knapsack problem to the problem you specified:

-specification of my knapsack problem:

1- assume you have two knapsacks which both have size c.

2- you have n items, with volumes v1, v2, .. vn.

3- you want to disturb all of these n items into your knapsacks.

-reducing this knapsack problem to your problem:

1- make a graph with (n + 1) vertices.

2- vertex i is connected to the vertex (i + 1) using two edges. one with cost vi (the volume of i'th item) and one with cost zero.

3- you want to find two edge disjoint path from vertex 1 to vertex (n + 1) with upper bound equal to knapsack size.

so if you could solve your problem in polynomial, the knapsack problem is solved in polynomial and you have proved P=NP. :D

of course according to above description, you may solve your problem in polynomial time in the edge weight of the graph, but it's a Pseudo-polynomial time algorithm, not a real one unlike Surballe's algorithm. sorry for bad English.