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.

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

##### MSC:

05C38 | Paths and cycles |

05C10 | Planar graphs; geometric and topological aspects of graph theory |

68Q25 | Analysis of algorithms and problem complexity |

PDF
BibTeX
XML
Cite

\textit{N. Robertson} and \textit{P. D. Seymour}, J. Comb. Theory, Ser. B 41, 115--138 (1986; Zbl 0598.05042)

Full Text:
DOI

##### References:

[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 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.