Almost Polynomial Hardness of Node-Disjoint Paths in Grids
by Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat
Theory of Computing, Volume 17(6), pp. 1-57, 2021
Bibliography with links to cited articles
[1] Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein: Inapproximabilty of densest k-subgraph from average case hardness, 2011. Manuscript.
[2] Noga Alon, Paul Seymour, and Robin Thomas: Planar separators. SIAM J. Discr. Math., 7(2):184–193, 1994. [doi:10.1137/S0895480191198768]
[3] Matthew Andrews: Approximation algorithms for the edge-disjoint paths problem via Raecke decompositions. In Proc. 51st FOCS, pp. 277–286. IEEE Comp. Soc., 2010. [doi:10.1109/FOCS.2010.33]
[4] Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, and Lisa Zhang: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica, 30(5):485–520, 2010. [doi:10.1007/s00493-010-2455-9]
[5] Matthew Andrews and Lisa Zhang: Logarithmic hardness of the undirected edge-disjoint paths problem. J. ACM, 53(5):745–761, 2006. [doi:10.1145/1183907.1183910]
[6] Yonatan Aumann and Yuval Rabani: Improved bounds for all optical routing. In Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’95), pp. 567–576. SIAM, 1995. ACM DL.
[7] Baruch Awerbuch, Rainer Gawlick, Tom Leighton, and Yuval Rabani: On-line admission control and circuit routing for high performance computing and communication. In Proc. 35th FOCS, pp. 412–423. IEEE Comp. Soc., 1994. [doi:10.1109/SFCS.1994.365675]
[8] Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan: Detecting high log-densities: an O(n1∕4) approximation for densest k-subgraph. In Proc. 42nd STOC, pp. 201–210. ACM Press, 2010. [doi:10.1145/1806689.1806719]
[9] Andrei Z. Broder, Alan M. Frieze, Stephen Suen, and Eli Upfal: Optimal construction of edge-disjoint paths in random graphs. SIAM J. Comput., 28(2):541–573, 1998. [doi:10.1137/S0097539795290805]
[10] Andrei Z. Broder, Alan M. Frieze, and Eli Upfal: Existence and construction of edge disjoint paths on expander graphs. SIAM J. Comput., 23(5):976–989, 1994. Preliminary version in STOC’92. [doi:10.1137/S0097539792232021]
[11] Chandra Chekuri and Alina Ene: Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 326–341. SIAM, 2013. [doi:10.1137/1.9781611973105.24]
[12] Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd: Multicommodity flow, well-linked terminals, and routing problems. In Proc. 37th STOC, pp. 183–192. ACM Press, 2005. [doi:10.1145/1060590.1060618]
[13] Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd: An O() approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2(7):137–146, 2006. [doi:10.4086/toc.2006.v002a007]
[14] Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd: Edge-disjoint paths in planar graphs with constant congestion. SIAM J. Comput., 39(1):281–301, 2009. Preliminary version in STOC’06. [doi:10.1137/060674442]
[15] Chandra Chekuri, Marcelo Mydlarz, and F. Bruce Shepherd: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms, 3(3):27:1–27:23, 2007. [doi:10.1145/1273340.1273343]
[16] Julia Chuzhoy: Routing in undirected graphs with constant congestion. SIAM J. Comput., 45(4):1490–1532, 2016. [doi:10.1137/130910464]
[17] Julia Chuzhoy and David Hong Kyun Kim: On approximating node-disjoint paths in grids. In Proc. 18th Internat. Workshop on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’15), pp. 187–211. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.187]
[18] Julia Chuzhoy, David Hong Kyun Kim, and Shi Li: Improved approximation for node-disjoint paths in planar graphs. In Proc. 48th STOC, pp. 556–569. ACM Press, 2016. [doi:10.1145/2897518.2897538]
[19] Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat: New hardness results for routing on disjoint paths. In Proc. 49th STOC, pp. 86–99. ACM Press, 2017. [doi:10.1145/3055399.3055411]
[20] Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat: Almost polynomial hardness of node-disjoint paths in grids. In Proc. 50th STOC, pp. 1220–1233. ACM Press, 2018. [doi:10.1145/3188745.3188772]
[21] Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat: Improved approximation for node-disjoint paths in grids with sources on the boundary. In Proc. 45th Internat. Colloq. on Automata, Languages, and Programming (ICALP’18), pp. 38:1–38:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ICALP.2018.38]
[22] Julia Chuzhoy and Shi Li: A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. J. ACM, 63(5):45:1–45:51, 2016. Preliminary version in FOCS’12. [doi:10.1145/2893472]
[23] Shimon Even, Alon Itai, and Adi Shamir: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., 5(4):691–703, 1976. [doi:10.1137/0205048]
[24] Uriel Feige: Relations between average case complexity and approximation complexity. In Proc. 34th STOC, pp. 534–543. ACM Press, 2002. [doi:10.1145/509907.509985]
[25] Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, and Aravind Srinivasan: Approximating the domatic number. SIAM J. Comput., 32(1):172–195, 2002. [doi:10.1137/S0097539700380754]
[26] Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase: New algorithms for maximum disjoint paths based on tree-likeness. Math. Programming, 171:433–461, 2018. Preliminary version in ESA’16. [doi:10.1007/s10107-017-1199-3]
[27] Alan M. Frieze: Edge-disjoint paths in expander graphs. SIAM J. Comput., 30(6):1790–1801, 2001. Preliminary version in SODA’00. [doi:10.1137/S0097539700366103]
[28] Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3–20, 1997. [doi:10.1007/BF02523685]
[29] Thomas Holenstein: Parallel repetition: Simplification and the no-signaling case. Theory of Computing, 5(8):141–172, 2009. Preliminary version in STOC’07. [doi:10.4086/toc.2009.v005a008]
[30] Richard Karp: On the complexity of combinatorial problems. Networks, 5(1):45–68, 1975. [doi:10.1002/net.1975.5.1.45]
[31] Ken-Ichi Kawarabayashi and Yusuke Kobayashi: An O(log n)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs. ACM Trans. Algorithms, 9(2):16:1–16:13, 2013. [doi:10.1145/2438645.2438648]
[32] Subhash Khot: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput., 36(4):1025–1071, 2006. [doi:10.1137/S0097539705447037]
[33] Jon Kleinberg: An approximation algorithm for the disjoint paths problem in even-degree planar graphs. In Proc. 46th FOCS, pp. 627–636. IEEE Comp. Soc., 2005. [doi:10.1109/SFCS.2005.18]
[34] Jon Kleinberg and Ronitt Rubinfeld: Short paths in expander graphs. In Proc. 37th FOCS, pp. 86–95. IEEE Comp. Soc., 1996. [doi:10.1109/SFCS.1996.548467]
[35] Jon M. Kleinberg and Éva Tardos: Disjoint paths in densely embedded graphs. In Proc. 36th FOCS, pp. 52–61. IEEE Comp. Soc., 1995. [doi:10.1109/SFCS.1995.492462]
[36] Jon M. Kleinberg and Éva Tardos: Approximations for the disjoint paths problem in high-diameter planar networks. J. Comput. System Sci., 57(1):61–73, 1998. [doi:10.1006/jcss.1998.1579]
[37] Stavros G. Kolliopoulos and Clifford Stein: Approximating disjoint-path problems using packing integer programs. Math. Programming, 99(1):63–87, 2004. [doi:10.1007/s10107-002-0370-6]
[38] Mark R. Kramer and Jan van Leeuwen: The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. Adv. Comput. Res., 2:129–146, 1984.
[39] Tom Leighton and Satish Rao: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787–832, 1999. [doi:10.1145/331524.331526]
[40] Richard J. Lipton and Robert Endre Tarjan: A separator theorem for planar graphs. SIAM J. Appl. Math., 36(2):177–189, 1979. [doi:10.1137/0136016]
[41] James F. Lynch: The equivalence of theorem proving and the interconnection problem. SIGDA Newsl., 5(3):31–36, 1975. [doi:10.1145/1061425.1061430]
[42] Pasin Manurangsi: Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. In Proc. 49th STOC, pp. 954–961. ACM Press, 2017. [doi:10.1145/3055399.3055412]
[43] Harald Räcke: Minimizing congestion in general networks. In Proc. 43rd FOCS, pp. 43–52. IEEE Comp. Soc., 2002. [doi:10.1109/SFCS.2002.1181881]
[44] Prabhakar Raghavan and Clark D. Thompson: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365–374, 1987. [doi:10.1007/BF02579324]
[45] Prasad Raghavendra and David Steurer: Graph expansion and the unique games conjecture. In Proc. 42nd STOC, pp. 755–764. ACM Press, 2010. [doi:10.1145/1806689.1806792]
[46] Anup Rao: Parallel repetition in projection games and a concentration bound. SIAM J. Comput., 40(6):1871–1891, 2011. Preliminary version in STOC’08. [doi:10.1137/080734042]
[47] Satish Rao and Shuheng Zhou: Edge disjoint paths in moderately connected graphs. SIAM J. Comput., 39(5):1856–1887, 2010. [doi:10.1137/080715093]
[48] Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. [doi:10.1137/S0097539795280895]
[49] Neil Robertson and Paul D. Seymour: Outline of a disjoint paths algorithm. In Paths, Flows and VLSI-Layout. Springer, 1990. WorldCat.org.
[50] Neil Robertson and Paul D. Seymour: Graph minors. XIII. The disjoint paths problem. J. Combin. Theory–B, 63(1):65–110, 1995. [doi:10.1006/jctb.1995.1006]
[51] Loïc Séguin-Charbonneau and F. Bruce Shepherd: Maximum edge-disjoint paths in planar graphs with congestion 2. Math. Programming, 188:295–317, 2021. Preliminary version in FOCS’11. [doi:10.1007/s10107-020-01513-1]
[52] Peter Ungar: A theorem on planar graphs. J. London Math. Soc., 26(4):256–262, 1951. [doi:10.1112/jlms/s1-26.4.256]