Document Open Access Logo

On Approximating Node-Disjoint Paths in Grids

Authors Julia Chuzhoy, David H. K. Kim

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.187.pdf
  • Filesize: 1.73 MB
  • 25 pages

Document Identifiers

Author Details

Julia Chuzhoy
David H. K. Kim

Cite As Get BibTex

Julia Chuzhoy and David H. K. Kim. On Approximating Node-Disjoint Paths in Grids. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 187-211, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.187

Abstract

In the Node-Disjoint Paths (NDP) problem, the input is an undirected n-vertex graph G, and a collection {(s_1,t_1),...,(s_k,t_k)} of pairs of vertices called demand pairs. The goal is to route the largest possible number of the demand pairs (s_i,t_i), by selecting a path connecting each such pair, so that the resulting paths are node-disjoint. NDP is one of the most basic and extensively studied routing problems. Unfortunately, its approximability is far from being well-understood: the best current upper bound of O(sqrt(n)) is achieved via a simple greedy algorithm, while the best current lower bound on its approximability is Omega(log^{1/2-\delta}(n)) for any constant delta. Even for seemingly simpler special cases, such as planar graphs, and even grid graphs, no better approximation algorithms are currently known. A major reason for this impasse is that the standard technique for designing approximation algorithms for routing problems is LP-rounding of the standard multicommodity flow relaxation of the problem, whose integrality gap for NDP is Omega(sqrt(n)) even on grid graphs.

Our main result is an O(n^{1/4} * log(n))-approximation algorithm for NDP on grids. We distinguish between demand pairs with both vertices close to the grid boundary, and pairs where at least one of the two vertices is far from the grid boundary. Our algorithm shows that when all demand pairs are of the latter type, the integrality gap of the multicommodity flow LP-relaxation is at most O(n^{1/4} * log(n)), and we deal with demand pairs of the former type by other methods. We complement our upper bounds by proving that NDP is APX-hard  on grid graphs.

Subject Classification

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

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, February 2000. Google Scholar
  2. M. Ajtai, V. Chvátal, M.M. Newborn, and E. Szemerédi. Crossing-free subgraphs. In Gert Sabidussi Peter L. Hammer, Alexander Rosa and Jean Turgeon, editors, Theory and Practice of Combinatorics A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday, volume 60 of North-Holland Mathematics Studies, pages 9-12. North-Holland, 1982. Google Scholar
  3. Matthew Andrews. Approximation algorithms for the edge-disjoint paths problem via Raecke decompositions. In Proceedings of IEEE FOCS, pages 277-286, 2010. Google Scholar
  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. Google Scholar
  5. Matthew Andrews and Lisa Zhang. Hardness of the undirected edge-disjoint paths problem. In STOC, pages 276-283. ACM, 2005. Google Scholar
  6. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45:501-555, May 1998. Google Scholar
  7. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of np. J. ACM, 45:70-122, January 1998. Google Scholar
  8. 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. Google Scholar
  9. Chandra Chekuri and Julia Chuzhoy. Half-integral all-or-nothing flow. Unpublished Manuscript. Google Scholar
  10. 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
  11. 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
  12. 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
  13. 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. Google Scholar
  14. Julia Chuzhoy. Routing in undirected graphs with constant congestion. In Proc. of ACM STOC, pages 855-874, 2012. Google Scholar
  15. Julia Chuzhoy and Shi Li. A polylogarithimic approximation algorithm for edge-disjoint paths with congestion 2. In Proc. of IEEE FOCS, 2012. Google Scholar
  16. M. Cutler and Y. Shiloach. Permutation layout. Networks, 8:253-278, 1978. Google Scholar
  17. R. Karp. On the complexity of combinatorial problems. Networks, 5:45-68, 1975. Google Scholar
  18. 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, March 2013. Google Scholar
  19. Jon M. Kleinberg. An approximation algorithm for the disjoint paths problem in even-degree planar graphs. In FOCS'05, pages 627-636, 2005. Google Scholar
  20. 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
  21. 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. Google Scholar
  22. Stavros G. Kolliopoulos and Clifford Stein. Approximating disjoint-path problems using packing integer programs. Mathematical Programming, 99:63-87, 2004. Google Scholar
  23. Frank Thomson Leighton. Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks. MIT Press, Cambridge, MA, USA, 1983. Google Scholar
  24. Harald Räcke. Minimizing congestion in general networks. In Proc. of IEEE FOCS, pages 43-52, 2002. Google Scholar
  25. Prabhakar Raghavan and Clark D. Tompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7:365-374, December 1987. Google Scholar
  26. Satish Rao and Shuheng Zhou. Edge disjoint paths in moderately connected graphs. SIAM J. Comput., 39(5):1856-1887, 2010. Google Scholar
  27. N. Robertson and P. D. Seymour. Outline of a disjoint paths algorithm. In Paths, Flows and VLSI-Layout. Springer-Verlag, 1990. Google Scholar
  28. Neil Robertson and Paul D. Seymour. Graph minors. VII. disjoint paths on a surface. J. Comb. Theory, Ser. B, 45(2):212-254, 1988. Google Scholar
  29. 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
  30. 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. Google Scholar
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 About DROPS Imprint Privacy Contact