zbMATH — the first resource for mathematics

Graph minors. VI. Disjoint paths across a disc. (English) Zbl 0598.05042
[For part V see the authors’ paper ibid. 41, 92-114 (1986; Zbl 0598.05055).]
Given a graph G and a finite set of pairs of vertices, do there exist vertex-disjoint paths joining each pair? This decision problem, DISJOINT CONNECTING PATHS, is known to be NP-complete, even for planar graphs. In this paper it is shown to be polynomial in two special cases: when G is drawn either on a disc or on a cylinder, all specified vertices always lying on the boundary.
In fact the authors derive a structural characterization, leading to a polynomial algorithm, for the more general DISJOINT CONNECTING SUBGRAPHS problem. Here pairs of vertices are replaced by pairwise disjoint subsets of vertices, and it is asked to decide whether a forest may be found in G with these subsets as vertex sets of its subtrees.
Fundamentally the method on the disk relies on several reduction steps, which usually reduce the number of vertices of the base graph, and, when these no longer apply, a move to some dual graph, permitting further reductions. In the cylindrical case the question reduces to the analogous one of finding a set of disjoint links between both boundaries, having a prespecified winding number. This is solved by the explicit construction of the set of realizable winding numbers.
Reviewer: F.Plastria

05C38 Paths and cycles
05C10 Planar graphs; geometric and topological aspects of graph theory
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Karp, R.M, On the computational complexity of combinatorial problems, Networks, 5, 45-68, (1975) · Zbl 0324.05003
[2] Lynch, J.F, The equivalence of theorem proving and the interconnection problem, ACM SIGMA newsletter, 5, 3, 31-65, (1975)
[3] {\scN. Robertson and P. D. Seymour}, Graph minors. VII. Disjoint paths on a surface, submitted for publication. · Zbl 0658.05044