Disjoint paths - a survey.

*(English)*Zbl 0565.05045Given 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 |

##### Keywords:

vertex-disjoint paths
PDF
BibTeX
XML
Cite

\textit{N. Robertson} and \textit{P. D. Seymour}, SIAM J. Algebraic Discrete Methods 6, 300--305 (1985; Zbl 0565.05045)

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 |

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

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.