[sci.math] Disjoint Paths Problem

grant@garfield.cs.mun.ca (Grant Burton) (03/21/91)

This is a 'famous' problem of Neil Robertson and P. D. Seymour.
  DISJOINT CONNECTING PATHS (DCP)
  -------------------------------
  INSTANCE: A graph G = (V,E), and pairs (s1,t1), ..., (sk,tk) of V.
  QUESTION: Do there exist paths P1, ..., Pk of G, mutually vertex-disjoint,
            such that Pi joins si and ti (1 <= i <= k) ?

The following is a problem I am working on, first some definitions.
1)  A path Pi is specified as <v(i), a(i,1), ..., a(i,*), u(i)>, such
	that the sequence indicates, in the usual fashion, which edges compose
    the path. The vertices a(*,*) are called internal vertices of Pi.
    The endpoints of the path are v(i) and u(i).
2)  Two paths Pi and Pj are called internally-disjoint iff their internal
    vertices are all mutually disjoint, formally speaking
    a(i,*) != a(j,*) for all a(i,*) in Pi and all a(j,*) in Pj. 
    Note that Pi and Pj may share at most one common endpoint, so this is
    different than the definition of vertex-disjoint paths as in DCP.
    
Now to define my problem.
  INTERNALLY DISJOINT CONNECTING PATHS (IDCP)
  -------------------------------------------
  INSTANCE: A graph G = (V,E), and pairs (s1,t1), ..., (sk,tk) of V.
  QUESTION: Do there exist paths P1, ..., Pk of G, mutually internally-
            disjoint, such that Pi has endspoints s1 and t1 (1 <= i <= k) ?

Questions:
1) These two problems are obviously different, do you agree ?
2) DCP is known to be NP-complete, and it is a subproblem of IDCP, 
   therefore IDCP must also NP-complete, do you agree ?
3) Have you ever heard of this IDCP problem before ?
4) Any general comments on an algorithm to solve this problem ?

Please e-mail your answers to me at grant@garfield.cs.mun.ca

          Thank You,

          Grant Burton
          Department of Computer Science
          Memorial University of Newfoundland
          St. John's, Newfoundland
          A1C 5S7

-- 
|   grant@garfield.cs.mun.ca
|   Man said "let there be light", and there was fire. Man being lonely created
|   machine in the image of himself, and chaos was discovered.

foster@ted.cs.uidaho.edu (03/23/91)

In article <1991Mar20.170612.13200@garfield.cs.mun.ca> grant@garfield.cs.mun.ca (Grant Burton) writes:
>
>Questions:
>2) DCP is known to be NP-complete, and it is a subproblem of IDCP, 
>   therefore IDCP must also NP-complete, do you agree ?

No.  2-sat is a subproblem of 3-sat, yet is not np-complete.

James