×

Disjoint paths - a survey. (English) Zbl 0565.05045

Given a graph G and pairs \((s_ 1,t_ 1),...,(s_ k,t_ k)\) of vertices, consider the problem of deciding the existence of pairwise vertex-disjoint paths \(P_ 1,...,P_ k\) of G such that \(P_ i\) has ends \(s_ i\) and \(t_ i\). A polynomial algorithm has been shown to exist for \(k=2\) by P. D. Seymour [Discrete Math. 29, 293-309 (1980; Zbl 0457.05043)] and, independently, Y. Shiloach [J. Assoc. Comput. Mach. 27, 445-456 (1980; Zbl 0475.68042)] but whether such exists for \(k\geq 3\) is not known. Here a polynomial algorithm that suffices for planar G and fixed k is described. The second problem considered is that of determining whether a prescribed graph H can be obtained from some subgraph of a graph G by contraction. As before, a polynomial algorithm exists if H is planar. The authors point out that in both cases the algorithms may not be practical because of the large degrees of the polynomials. Detailed proofs of these results are to appear elsewhere.
Reviewer: R.C.Entringer

MSC:

05C38 Paths and cycles
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
Full Text: DOI

References:

[1] Dirac, G. A., A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc., 27, 85, (1952) · Zbl 0046.41001
[2] Fortune, Steven; Hopcroft, John; Wyllie, James, The directed subgraph homeomorphism problem, Theoret. Comput. Sci., 10, 111, (1980) · Zbl 0419.05028 · doi:10.1016/0304-3975(80)90009-2
[3] Karp, R. M., On the complexity of combinatorial problems, Networks, 5, 45, (1975) · Zbl 0324.05003
[4] Lynch, J. F., The equivalence of theorem proving and the interconnection problem, ACM SIGDA Newsletter, 5:3, (1976)
[5] Robertson, Neil; Seymour, P. D., Graph minors. II. algorithmic aspects of tree-width, J. Algorithms, 7, 309, (1986) · Zbl 0611.05017
[6] Robertson, Neil; Seymour, P. D., Graph minors. IV. tree-width and well-quasi-ordering, J. Combin. Theory Ser. B, 48, 227, (1990) · Zbl 0719.05032
[7] Robertson, Neil; Seymour, P. D., Graph minors. V. excluding a planar graph, J. Combin. Theory Ser. B, 41, 92, (1986) · Zbl 0598.05055
[8] Robertson, Neil; Seymour, P. D., Graph minors. VI. disjoint paths across a disc, J. Combin. Theory Ser. B, 41, 115, (1986) · Zbl 0598.05042
[9] Robertson, Neil; Seymour, P. D., Graph minors. VII. disjoint paths on a surface, J. Combin. Theory Ser. B, 45, 212, (1988) · Zbl 0658.05044
[10] Seymour, P. D., Disjoint paths in graphs, Discrete Math., 29, 293, (1980) · Zbl 0457.05043
[11] Shiloach, Yossi, A polynomial solution to the undirected two paths problem, J. Assoc. Comput. Mach., 27, 445, (1980) · Zbl 0475.68042 · doi:10.1145/322203.322207
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.