×

The disjoint paths problem in quadratic time. (English) Zbl 1298.05296

Summary: 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 L. Perković and B. Reed announced in [Int. J. Found. Comput. Sci. 11, No. 3, 365–371 (2000; doi:10.1142/S0129054100000247); Lect. Notes Comput. Sci. 1665, 148–154 (1999; Zbl 0945.05054)] (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.

MSC:

05C83 Graph minors
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0945.05054
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial \(k\)-trees, Discrete Appl. Math., 23, 11-24 (1989) · Zbl 0666.68067
[2] Bodlaender, H. L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 1305-1317 (1996) · Zbl 0864.68074
[3] Chekuri, C.; Khanna, S.; Shepherd, B., The all-or-nothing multicommodity flow problem, (Proc. 36th ACM Symposium on Theory of Computing (STOC) (2004)), 156-165 · Zbl 1192.68878
[4] Chekuri, C.; Khanna, S.; Shepherd, B., Edge-disjoint paths in planar graphs, (Proc. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2004)), 71-80
[5] Chekuri, C.; Khanna, S.; Shepherd, B., Multicommodity flow, well-linked terminals, and routing problems, (Proc. 37th ACM Symposium on Theory of Computing (STOC) (2005)), 183-192 · Zbl 1192.90017
[6] Chekuri, C.; Khanna, S.; Shepherd, B., Edge-disjoint paths in planar graphs with constant congestion, (Proc. 38th ACM Symposium on Theory of Computing (STOC) (2006)), 757-766 · Zbl 1301.68268
[7] Diestel, R.; Gorbunov, K. Y.; Jensen, T. R.; Thomassen, C., Highly connected sets and the excluded grid theorem, J. Combin. Theory Ser. B, 75, 61-73 (1999) · Zbl 0949.05075
[8] Dvořák, Z.; Králʼ, D.; Thomas, R., Coloring triangle-free graphs on surfaces, (ACM-SIAM Symposium on Discrete Algorithms (SODA) (2009)), 120-129 · Zbl 1423.05065
[9] Frank, A., Packing paths, cuts and circuits - a survey, (Korte, B.; Lovász, L.; Prömel, H. J.; Schrijver, A., Paths, Flows, VLSI-Layout (1990), Springer-Verlag: Springer-Verlag Berlin), 49-100 · Zbl 0741.05042
[10] Halin, R., \(S\)-functions for graphs, J. Geom., 8, 171-186 (1976) · Zbl 0339.05108
[11] R. Kapadia, Z. Li, B. Reed, Two disjoint rooted paths in linear time, preprint.; R. Kapadia, Z. Li, B. Reed, Two disjoint rooted paths in linear time, preprint.
[12] Karp, R. M., On the computational complexity of combinatorial problems, Networks, 5, 45-68 (1975) · Zbl 0324.05003
[13] Kawarabayashi, K.; Reed, B., A nearly linear time algorithm for the half integral disjoint paths packing, (ACM-SIAM Symposium on Discrete Algorithms (SODA) (2008)), 446-454 · Zbl 1192.05161
[14] Kawarabayashi, K.; Wollan, P., A shorter proof of the graph minors algorithm - the unique linkage theorem, (Proc. 42nd ACM Symposium on Theory of Computing (STOC) (2010)), 687-694, A detailed version of this paper is available at · Zbl 1293.05363
[15] Kleinberg, J., Single-source unsplittable flow, (Proc. 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (1996)), 68-77
[16] Kleinberg, J., Decision algorithms for unsplittable flow and the half-disjoint paths problem, (Proc. 30th ACM Symposium on Theory of Computing (STOC) (1998)), 530-539 · Zbl 1028.68217
[17] Kleinberg, J.; Tardos, É., Disjoint paths in densely embedded graphs, (Proc. 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (1995)), 52-61 · Zbl 0938.68752
[18] Kleinberg, J.; Tardos, É., Approximations for the disjoint paths problem in high-diameter planar networks, J. Comput. System Sci., 57, 61-73 (1998) · Zbl 0912.68151
[19] Kobayashi, Y.; Kawarabayashi, K., Algorithms for finding an induced cycle in planar graphs and bounded genus graphs, (ACM-SIAM Symposium on Discrete Algorithms (SODA) (2009)), 1146-1155 · Zbl 1423.05179
[20] Kolliopoulos, S.; Stein, C., Improved approximation algorithms for unsplittable flow problems, (Proc. 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (1997)), 426-435
[21] Lynch, J. F., The equivalence of theorem proving and the interconnection problem, ACM SIGDA Newsletter, 5, 31-65 (1975)
[22] Middendorf, M.; Pfeiffer, F., On the complexity of the disjoint paths problem, Combinatorica, 13, 97-107 (1993) · Zbl 0770.68072
[23] Nagamochi, H.; Ibaraki, T., A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph, Algorithmica, 7, 583-596 (1992) · Zbl 0763.05065
[24] Perković, L.; Reed, B., An improved algorithm for finding tree decompositions of small width, Internat. J. Found. Comput. Sci., 11, 365-371 (2000) · Zbl 1320.05128
[25] Reed, B., Finding approximate separators and computing tree width quickly, (Proc. 24th ACM Symposium on Theory of Computing (STOC) (1992)), 221-228
[26] Reed, B., Rooted routing in the plane, Discrete Appl. Math., 57, 213-227 (1995) · Zbl 0816.05050
[27] Reed, B., Tree width and tangles: a new connectivity measure and some applications, (Surveys in Combinatorics. Surveys in Combinatorics, London Math. Soc. Lecture Notes Series, vol. 241 (1997), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 87-162 · Zbl 0895.05034
[28] Reed, B.; Wood, D. R., A linear-time algorithm to find a separator in a graph excluding a minor, ACM Trans. Algorithms, 5, 39 (2009) · Zbl 1298.05308
[29] Reed, B.; Robertson, N.; Schrijver, A.; Seymour, P. D., Finding disjoint trees in planar graphs in linear time, (Contemp. Math., vol. 147 (1993), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 295-301 · Zbl 0791.05092
[30] Robertson, N.; Seymour, P. D., Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7, 309-322 (1986) · Zbl 0611.05017
[31] Robertson, N.; Seymour, P. D., Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B, 41, 92-114 (1986) · Zbl 0598.05055
[32] Robertson, N.; Seymour, P. D., An outline of a disjoint paths algorithm, (Korte, B.; Lovász, L.; Prömel, H. J.; Schrijver, A., Paths, Flows, and VLSI-Layout (1990), Springer-Verlag: Springer-Verlag Berlin), 267-292 · Zbl 0759.05055
[33] Robertson, N.; Seymour, P. D., Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63, 65-110 (1995) · Zbl 0823.05038
[34] Robertson, N.; Seymour, P. D., Graph minors. XVI. Excluding a non-planar graph, J. Combin. Theory Ser. B, 89, 43-76 (2003) · Zbl 1023.05040
[35] Robertson, N.; Seymour, P., Graph minors. XXI. Graphs with unique linkages, J. Combin. Theory Ser. B, 99, 583-616 (2009) · Zbl 1229.05253
[36] Robertson, N.; Seymour, P. D.; Thomas, R., Quickly excluding a planar graph, J. Combin. Theory Ser. B, 62, 323-348 (1994) · Zbl 0807.05023
[37] Seymour, P. D., Disjoint paths in graphs, Discrete Math., 29, 293-309 (1980) · Zbl 0457.05043
[38] Tarjan, R. E., Data Structures and Network Algorithms (1983), SIAM: SIAM Philadelphia, PA · Zbl 0584.68077
[39] Tholey, T., Solving the 2-disjoint paths problem in nearly linear time, Theory Comput. Syst., 39, 51-78 (2006) · Zbl 1103.68100
[40] Tholey, T., Improved algorithms for the 2-vertex disjoint paths problem, (Proc. 35th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). Proc. 35th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), LNCS, vol. 5404 (2009)), 546-557 · Zbl 1206.68243
[41] Thomassen, C., 2-Linked graphs, European J. Combin., 1, 371-378 (1980) · Zbl 0457.05044
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.