# 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.

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 |