Document Open Access Logo

Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary

Authors Julia Chuzhoy, David H. K. Kim, Rachit Nimavat

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.38.pdf
  • Filesize: 0.66 MB
  • 14 pages

Document Identifiers

Author Details

Julia Chuzhoy
  • Toyota Technological Institute at Chicago, 6045 S. Kenwood Ave., Chicago, Illinois 60637, USA
David H. K. Kim
  • Computer Science Department, University of Chicago, 1100 East 58th Street, Chicago, Illinois 60637, USA
Rachit Nimavat
  • Toyota Technological Institute at Chicago, 6045 S. Kenwood Ave., Chicago, Illinois 60637, USA

Funding

  • Chuzhoy, Julia: Supported in part by NSF grants CCF-1318242 and CCF-1616584.
  • Kim, David H. K.: Supported in part by NSF grants CCF-1318242 and CCF-1616584.
  • Nimavat, Rachit: Supported in part by NSF grant CCF-1318242.

Cite AsGet BibTex

Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.38

Abstract

We study the classical Node-Disjoint Paths (NDP) problem: given an undirected n-vertex graph G, together with a set {(s_1,t_1),...,(s_k,t_k)} of pairs of its vertices, called source-destination, or demand pairs, find a maximum-cardinality set {P} of mutually node-disjoint paths that connect the demand pairs. The best current approximation for the problem is achieved by a simple greedy O(sqrt{n})-approximation algorithm. Until recently, the best negative result was an Omega(log^{1/2-epsilon}n)-hardness of approximation, for any fixed epsilon, under standard complexity assumptions. A special case of the problem, where the underlying graph is a grid, has been studied extensively. The best current approximation algorithm for this special case achieves an O~(n^{1/4})-approximation factor. On the negative side, a recent result by the authors shows that NDP is hard to approximate to within factor 2^{Omega(sqrt{log n})}, even if the underlying graph is a subgraph of a grid, and all source vertices lie on the grid boundary. In a very recent follow-up work, the authors further show that NDP in grid graphs is hard to approximate to within factor Omega(2^{log^{1-epsilon}n}) for any constant epsilon under standard complexity assumptions, and to within factor n^{Omega(1/(log log n)^2)} under randomized ETH. In this paper we study the NDP problem in grid graphs, where all source vertices {s_1,...,s_k} appear on the grid boundary. Our main result is an efficient randomized 2^{O(sqrt{log n}* log log n)}-approximation algorithm for this problem. Our result in a sense complements the 2^{Omega(sqrt{log n})}-hardness of approximation for sub-graphs of grids with sources lying on the grid boundary, and should be contrasted with the above-mentioned almost polynomial hardness of approximation of NDP in grid graphs (where the sources and the destinations may lie anywhere in the grid). Much of the work on approximation algorithms for NDP relies on the multicommodity flow relaxation of the problem, which is known to have an Omega(sqrt n) integrality gap, even in grid graphs, with all source and destination vertices lying on the grid boundary. Our work departs from this paradigm, and uses a (completely different) linear program only to select the pairs to be routed, while the routing itself is computed by other methods.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • Node-disjoint paths
  • approximation algorithms
  • routing and layout

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alok Aggarwal, Jon Kleinberg, and David P. Williamson. Node-disjoint paths on the mesh and a new trade-off in VLSI layout. SIAM J. Comput., 29(4):1321-1333, 2000. URL: http://dx.doi.org/10.1137/S0097539796312733.
  2. Matthew Andrews. Approximation algorithms for the edge-disjoint paths problem via Raecke decompositions. In Proceedings of IEEE FOCS, pages 277-286, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.33.
  3. 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. URL: http://dx.doi.org/10.1007/s00493-010-2455-9.
  4. Matthew Andrews and Lisa Zhang. Logarithmic hardness of the undirected edge-disjoint paths problem. J. ACM, 53(5):745-761, sep 2006. URL: http://dx.doi.org/10.1145/1183907.1183910.
  5. Yonatan Aumann and Yuval Rabani. Improved bounds for all optical routing. In Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, SODA '95, pages 567-576, Philadelphia, PA, USA, 1995. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=313651.313820.
  6. Chandra Chekuri and Julia Chuzhoy. Half-integral all-or-nothing flow. Unpublished Manuscript. Google Scholar
  7. Chandra Chekuri and Alina Ene. Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In Proc. of ACM-SIAM SODA, 2013. Google Scholar
  8. Chandra Chekuri, Sanjeev Khanna, and F Bruce Shepherd. Edge-disjoint paths in planar graphs. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 71-80. IEEE, 2004. Google Scholar
  9. Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. Multicommodity flow, well-linked terminals, and routing problems. In Proc. of ACM STOC, pages 183-192, 2005. Google Scholar
  10. Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. An O(√ n) approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2(1):137-146, 2006. URL: http://dx.doi.org/10.4086/toc.2006.v002a007.
  11. Julia Chuzhoy. Routing in undirected graphs with constant congestion. SIAM J. Comput., 45(4):1490-1532, 2016. URL: http://dx.doi.org/10.1137/130910464.
  12. Julia Chuzhoy and David H. K. Kim. On approximating node-disjoint paths in grids. In Naveen Garg, Klaus Jansen, Anup Rao, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, volume 40 of LIPIcs, pages 187-211. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://www.dagstuhl.de/dagpub/978-3-939897-89-7, URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.187.
  13. Julia Chuzhoy, David H. K. Kim, and Shi Li. Improved approximation for node-disjoint paths in planar graphs. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 556-569, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2897518.2897538.
  14. Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. Almost polynomial hardness of node-disjoint paths in grids. Unpublished Manuscript, 2017. Google Scholar
  15. Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. New hardness results for routing on disjoint paths. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 86-99. ACM, 2017. URL: http://dx.doi.org/10.1145/3055399.3055411.
  16. 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. URL: http://dl.acm.org/citation.cfm?id=2893472, URL: http://dx.doi.org/10.1145/2893472.
  17. M. Cutler and Y. Shiloach. Permutation layout. Networks, 8:253-278, 1978. URL: http://dx.doi.org/10.1002/net.3230080308.
  18. Shimon Even, Alon Itai, and Adi Shamir. On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., 5(4):691-703, 1976. URL: http://dx.doi.org/10.1137/0205048.
  19. Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase. New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness. In Piotr Sankowski and Christos Zaroliagis, editors, 24th Annual European Symposium on Algorithms (ESA 2016), volume 57 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1-42:17, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.42.
  20. R. Karp. On the complexity of combinatorial problems. Networks, 5:45-68, 1975. Google Scholar
  21. 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. URL: http://dx.doi.org/10.1145/2438645.2438648.
  22. Jon Kleinberg. An approximation algorithm for the disjoint paths problem in even-degree planar graphs. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS '05, pages 627-636, Washington, DC, USA, 2005. IEEE Computer Society. URL: http://dx.doi.org/10.1109/SFCS.2005.18.
  23. Jon M. Kleinberg and Éva Tardos. Disjoint paths in densely embedded graphs. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 52-61, 1995. Google Scholar
  24. Jon M. Kleinberg and Éva Tardos. Approximations for the disjoint paths problem in high-diameter planar networks. J. Comput. Syst. Sci., 57(1):61-73, 1998. URL: http://dx.doi.org/10.1006/jcss.1998.1579.
  25. Stavros G. Kolliopoulos and Clifford Stein. Approximating disjoint-path problems using packing integer programs. Mathematical Programming, 99:63-87, 2004. URL: http://dx.doi.org/10.1007/s10107-002-0370-6.
  26. MR Kramer and Jan van Leeuwen. The complexity of wire-routing and finding minimum area layouts for arbitrary vlsi circuits. Advances in computing research, 2:129-146, 1984. Google Scholar
  27. James F. Lynch. The equivalence of theorem proving and the interconnection problem. SIGDA Newsl., 5(3):31-36, 1975. URL: http://dx.doi.org/10.1145/1061425.1061430.
  28. Harald Räcke. Minimizing congestion in general networks. In Proc. of IEEE FOCS, pages 43-52, 2002. Google Scholar
  29. Prabhakar Raghavan and Clark D. Tompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7:365-374, December 1987. URL: http://dx.doi.org/10.1007/BF02579324.
  30. Satish Rao and Shuheng Zhou. Edge disjoint paths in moderately connected graphs. SIAM J. Comput., 39(5):1856-1887, 2010. URL: http://dx.doi.org/10.1137/080715093.
  31. N. Robertson and P. D. Seymour. Outline of a disjoint paths algorithm. In Paths, Flows and VLSI-Layout. Springer-Verlag, 1990. Google Scholar
  32. Neil Robertson and Paul D. Seymour. Graph minors. VII. disjoint paths on a surface. J. Comb. Theory, Ser. B, 45(2):212-254, 1988. URL: http://dx.doi.org/10.1016/0095-8956(88)90070-6.
  33. Neil Robertson and Paul D Seymour. Graph minors. XIII. the disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. Google Scholar
  34. Loïc Seguin-Charbonneau and F. Bruce Shepherd. Maximum edge-disjoint paths in planar graphs with congestion 2. In Proceedings of the 2011 IEEE 52Nd Annual Symposium on Foundations of Computer Science, FOCS '11, pages 200-209, Washington, DC, USA, 2011. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2011.30.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact