# zbMATH — the first resource for mathematics

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.

##### MSC:
 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
##### Keywords:
graph minors; disjoint paths problem; NP-complete
Full Text: