The disjoint paths problem in quadratic time

We consider the following well-known problem, which is called the disjoint paths problem. For a given graph G and a set of k pairs of terminals in G, the objective is to find k vertex-disjoint paths connecting given pairs of terminals or to conclude that such paths do not exist. 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. Note that Perkovic and Reed (2000) announced in [24] (without proofs) that this problem can be solved in O(n(2)) time. Our algorithm implies that there is an O(n(2)) time algorithm for the k edge-disjoint paths problem, the minor containment problem, and the labeled minor containment problem. 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. (C) 2011 Elsevier Inc. All rights reserved.