On the Complexity of the Disjoint Path Problem

Middendorf, Matthias and Pfeiffer, Frank (1993) On the Complexity of the Disjoint Path Problem.
Published in: Combinatorica Vol. 13 (1). pp. 97-107.

Abstract

We consider the disjoint paths problem. Given a graph G and a subset S of the edge-set of G the problem is to decide whether there exists a family F of disjoint circuits in G each containing exactly one edge of S such that every edge in S belongs to a circuit in C. By a well-known theorem of P. Seymour [On odd cuts and plane multicommodity flows, Proc. London Math. Soc.(3) 42, 178-192 (1981)] the edge-disjoint paths problem is polynomially solvable for Eulerian planar graphs G. We show that (assuming P e NP) one can drop neither planarity nor the Eulerian condition on G without losing polynomial time solvability. We prove the NP-completeness of the planar edge-disjoint paths problem by showing the NP-completeness of the vertex disjoint paths problem for planar graphs with maximum vertex-degree three. This disproves (assuming P e NP) a conjecture of A. Schrijver [Homotopic Routing Methods, in: Paths, Flows and VLSI Layout, Algorithms Comb. 9, 329-371 (1990)] concerning the existence of a polynomial time algorithm for the planar vertex-disjoint paths problem. Furthermore we present a counterexample to a conjugate of A. Frank mentioned in A. Seboe [Dual Integrality and Multicommodity Flows. Combinatorics, Colloquia Mathematica Societatis Janos Bolyai, 52, 453-469 (1988)]. This conjecture would have implied a polynomial algorithm for the planar edge-disjoint paths problem. Moreover we derive a complete characterization of all minor-closed classes of graphs for which the disjoint paths problem is polynomially solvable. Finally we show the NP-completeness of the half-integral relaxation of the edge-disjoint paths problem. This implies an answer to the long-standing question whether the edge-disjoint paths problem is polynomially solvable for Eulerian graphs.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr91-098
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 11:30
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/98