Graph minors. XIII: The disjoint paths problem (Q1892832)

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.