scientific article; zbMATH DE number 16300

[For the entire collection see Zbl 0719.00011.] The \(k\)-disjoint paths problem is the following: Given a graph \(G\) and \(2k\) vertices \(x_ 1,\dots,x_ k\), \(y_ 1,\dots,y_ k\). Does there exist, in \(G,k\) mutually vertex disjoint paths \(P_ 1,\dots,P_ k\) such that \(P_ i\) starts in \(x_ i\) and ends in \(y_ i\). It is well known that if \(k\) is part of the input, then this problem is NP-complete. Also if \(G\) is a directed graph, the problem is NP-complete, even when \(k=2\). For undirected graphs, it was shown independently by Seymour, Shiloach and Thomassen, that the case \(k=2\) is decidable by a simple algorithm. This remained the only solved case, until Robertson and Seymour used the power of their Graph Minors machinery, and were able to show that the \(k\)-disjoint paths problem is polynomiable solvable for any fixed \(k\). Furthermore the complexity of the algorithm is independent of \(k\), namely \(O(| V|^ 2| E|)\). One interesting aspect of their method is, that although the existence of a \(O(| V|^ 2| E|)\) algorithm is proved, the constants involved are so large, that the proposed algorithm has no practical use. Hence, there remains the interesting problem of finding, even in the case \(k=3\), a polynomial algorithm which can be used in practice. This paper gives an outline of the derivation of a polynomial algorithm from the Graph Minor machinery. Intuitively, a graph has tree-width \(\leq k\) if it can be constructed by piecing together graphs with at most \(k+1\) vertices in a tree-like structure. Trees have tree-width 1 and at the other extreme complete graphs have tree-width \(n-1\). The idea of the algorithm is that if the input graph has high enough tree-width, then one can find a so-called ``irrelevant vertex, one whose deletion does not change the problem. This step is repeated until the tree-width becomes too small. Now the graph is cut up by many low order separations, and these can be used to solve the problem directly. Thus the main step of the algorithm becomes that of identifying an irrelevant vertex. This part uses a result from one of the Graph Minor papers, that for every \(h\geq 0\), every graph of sufficiently high tree-width has a subgraph which is a wall of height \(h\). A wall of height \(h\) is a portion of the hexagonal lattice consisting of \(h\) horizontal paths and \(h\) edges between consecutive pairs of them; or a subdivision of such a graph. The problem of finding an irrelevant vertex, is now reduced to finding a very large wall, and then using that to find an irrelevant vertex. The proof that the algorithm really does locate an irrelevant vertex, requires all the machinery from the Graph Minors package.

Recommendations

Cited in

(40)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972953)