samir@umiacs.umd.edu (Samir Khuller) (02/19/91)
>Given a planar graph G=<V,E>, and four vertex s1,s2,t1,t2 in V, and integer K, >Is there a polynomial time algorithm to find two edge-disjoint paths (s1-- t1) >(s2--t2), whose total length is less than K edges (or whose total length is >minimized)? I would like to have a reference on this problem or any >generalization of it. Thanks a lot. Chingting Wu ******************************************************************************* A generalization of the problem does appear to be NP-complete: -------------- Consider the following variation: Given a graph (later we will see how to planarize it), and weights on the edges (let's say non-negative values); are there 2 disjoint paths (s1--t1 and s2--t2), such that the length of the larger path is <= K. (K is an upper bound on the lengths of both the paths). Reduction from PARTITION (Given a set A of values a1, a2 etc, is there a subset A' such that the size of A'=half the size of A (ie A/2)). Make the following graph: s1----------o---------o-----------o----------o----------o....o-------o------t1 \ / a1 \ / a2 \ . an \ / \ / \ / \ . \ . \ / \ / \ . . . \ / \ / \ . . . \ / \ / . . . . \/ \/ . . . . /\ / \ . . . / \ / \ / . . . / \ / \ / . \ / / \ / \ / . /\ / \ / \ / . / -\ s2-----------o---------o-----------o-----------o---------o....o-------o------t2 Thw weights on the edges are as shown, the other weights may be assumed to be zero. The two paths that go from s1 to t1 and s2 to t2, will naturally partition the set into two sets (one corresponding to the elements on each path). By setting K=A/2 we can find out if there is an exact partition or not. The graph can also be "planarized" by adding vertices at the crossing points. Notice that the sum of the path lengths is always A, so it doesnt really solve the original problem. (But it at least makes me believe that the original problem (with weights) is NP-Hard ! People who do discover a polynomial time algorithm for the original problem (sum of path lengths), may NOT claim to disprove Samir's conjecture :-)