We consider the following well-known problem, which is called the disjoint paths problem. Input: A graph G, k pairs of vertices (s 1 , t 1 ), (s 2 , t 2 ), . . . , (s k , t k ) in G (which are sometimes called terminals). Output : Vertex disjoint paths P 1 , . . . , P k in G such that P i joins s i and t i for i = 1, 2, . . . , k. We present an O(n 2 ) time algorithm for this problem for fixed k. This improves the time complexity of the seminal result by Robertson and Seymour, who gave an O(n 3 ) time algorithm for the disjoint paths problem for fixed k. Our algorithm implies that there is an O(n 2 ) time algorithm for the following problems: 1. The k edge disjoint paths problem, i.e., paths P 1 , . . . , P k are not vertex disjoint but edge disjoint. 2. The minor containment problem, i.e., for a fixed graph H and a given graph G, test whether or not G has a minor isomorphic to H. 3. The labelled minor containment problem, i.e., given a graph G and non-null subsets In fact, the time complexity of all the algorithms with the most expensive part depending on Robertson and Seymour's algorithm can be improved to O(n 2 ), for example, the membership testing for minor-closed class of graphs.
A result of Kawarabayashi-Kobayashi-Reed provides an O(n 2 ) time algorithm REF .
The disjoint paths problem in quadratic time
J. Comb. Theory, Ser. B
J. Comb. Theory, Ser. B
Computer Science Mathematics