Graph minors. XIII: The disjoint paths problem. (English) Zbl 0823.05038

This paper continues the authors’ landmark series on graph minors. For a graph \(G= (V, E)\) and vertices \(x_ 1,\dots, x_ k\) and \(y_ 1,\dots, y_ k\) in \(V\), the \(k\) disjoint paths problem is to decide whether or not paths \(P_ 1,\dots, P_ k\) can be found so that \(P_ i\) is a path between \(x_ i\) and \(y_ i\) so that two distinct paths \(P_ i\) and \(P_ j\) are vertex-disjoint. It is known that this problem is NP- complete in general; here an \(O(v^ 3)\) algorithm is developed to solve the \(k\) disjoint paths problem whenever \(k\) is fixed. Consequences for finding subdivisions or minors of a graph \(H\) in a graph \(G\) are examined.


05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI