Document Open Access Logo

A Local-To-Global Theorem for Congested Shortest Paths

Authors Shyan Akmal , Nicole Wein

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.8.pdf
  • Filesize: 0.85 MB
  • 17 pages

Document Identifiers

Author Details

Shyan Akmal
  • MIT, EECS and CSAIL, Cambridge, MA, USA
Nicole Wein
  • DIMACS, Rutgers University, Piscataway, NJ, USA

Funding

  • Akmal, Shyan: Supported in part by NSF grant CCF-2129139.
  • Wein, Nicole: Supported by a grant to DIMACS from the Simons Foundation (820931).

Acknowledgements

We thank Virginia Vassilevska Williams for helpful discussions about this work.

Cite AsGet BibTex

Shyan Akmal and Nicole Wein. A Local-To-Global Theorem for Congested Shortest Paths. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.8

Abstract

Amiri and Wargalla proved the following local-to-global theorem about shortest paths in directed acyclic graphs (DAGs): if G is a weighted DAG with the property that for each subset S of 3 nodes there is a shortest path containing every node in S, then there exists a pair (s,t) of nodes such that there is a shortest st-path containing every node in G. We extend this theorem to general graphs. For undirected graphs, we prove that the same theorem holds (up to a difference in the constant 3). For directed graphs, we provide a counterexample to the theorem (for any constant). However, we prove a roundtrip analogue of the theorem which guarantees there exists a pair (s,t) of nodes such that every node in G is contained in the union of a shortest st-path and a shortest ts-path. The original local-to-global theorem for DAGs has an application to the k-Shortest Paths with Congestion c ((k,c)-SPC) problem. In this problem, we are given a weighted graph G, together with k node pairs (s_1,t_1),… ,(s_k,t_k), and a positive integer c ≤ k, and tasked with finding a collection of paths P_1,… , P_k such that each P_i is a shortest path from s_i to t_i, and every node in the graph is on at most c paths P_i, or reporting that no such collection of paths exists. When c = k, there are no congestion constraints, and the problem can be solved easily by running a shortest path algorithm for each pair (s_i,t_i) independently. At the other extreme, when c = 1, the (k,c)-SPC problem is equivalent to the k-Disjoint Shortest Paths (k-DSP) problem, where the collection of shortest paths must be node-disjoint. For fixed k, k-DSP is polynomial-time solvable on DAGs and undirected graphs. Amiri and Wargalla interpolated between these two extreme values of c, to obtain an algorithm for (k,c)-SPC on DAGs that runs in polynomial time when k-c is constant. In the same way, we prove that (k,c)-SPC can be solved in polynomial time on undirected graphs whenever k-c is constant. For directed graphs, because of our counterexample to the original theorem statement, our roundtrip local-to-global result does not imply such an algorithm (k,c)-SPC. Even without an algorithmic application, our proof for directed graphs may be of broader interest because it characterizes intriguing structural properties of shortest paths in directed graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • disjoint paths
  • shortest paths
  • congestion
  • parameterized complexity

Metrics

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

Related Versions

References

  1. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 377-391. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch28.
  2. Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with congestion in acyclic digraphs. Inf. Process. Lett., 151, 2019. URL: https://doi.org/10.1016/j.ipl.2019.105836.
  3. Saeed Akhoondian Amiri and Julian Wargalla. Disjoint shortest paths with congestion on dags. CoRR, abs/2008.08368, 2020. URL: https://arxiv.org/abs/2008.08368.
  4. Matthew Andrews. Approximation algorithms for the edge-disjoint paths problem via raecke decompositions. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 277-286. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.33.
  5. Matthew Andrews and Lisa Zhang. Hardness of the undirected congestion minimization problem. SIAM J. Comput., 37(1):112-131, 2007. URL: https://doi.org/10.1137/050636899.
  6. Yossi Azar and Oded Regev. Combinatorial algorithms for the unsplittable flow problem. Algorithmica, 44(1):49-66, 2006. URL: https://doi.org/10.1007/s00453-005-1172-z.
  7. Alok Baveja and Aravind Srinivasan. Approximation algorithms for disjoint paths and related routing and packing problems. Math. Oper. Res., 25(2):255-280, 2000. URL: https://doi.org/10.1287/moor.25.2.255.12228.
  8. Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche. Using a Geometric Lens to Find k Disjoint Shortest Paths. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1-26:14, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.26.
  9. Kristóf Bérczi and Yusuke Kobayashi. The directed disjoint shortest paths problem. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pages 13:1-13:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.13.
  10. Aaron Bernstein and Nicole Wein. Closing the gap between directed hopsets and shortcut sets, 2022. URL: https://doi.org/10.48550/arXiv.2207.04507.
  11. Greg Bodwin. Linear size distance preservers. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 600-615. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.39.
  12. Greg Bodwin. On the structure of unique shortest paths in graphs. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2071-2089. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.125.
  13. Greg Bodwin and Gary Hoppenworth. Folklore sampling is optimal for exact hopsets: Confirming the √n barrier, 2023. URL: https://doi.org/10.48550/arXiv.2304.02193.
  14. Massimo Cairo, Roberto Grossi, and Romeo Rizzi. New bounds for approximating extremal distances in undirected graphs. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 363-376. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch27.
  15. Shiri Chechik and Tianyi Zhang. Nearly 2-approximate distance oracles in subquadratic time. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 551-580. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.26.
  16. Chandra Chekuri and Alina Ene. Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 326-341. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.24.
  17. 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. URL: https://doi.org/10.1137/060674442.
  18. Julia Chuzhoy. Routing in undirected graphs with constant congestion. SIAM J. Comput., 45(4):1490-1532, 2016. URL: https://doi.org/10.1137/130910464.
  19. Daniel Cizma and Nati Linial. Geodesic geometry on graphs. Discrete & Computational Geometry, 68(1):298-347, January 2022. URL: https://doi.org/10.1007/s00454-021-00345-w.
  20. Daniel Cizma and Nati Linial. Irreducible nonmetrizable path systems in graphs. Journal of Graph Theory, 102(1):5-14, June 2022. URL: https://doi.org/10.1002/jgt.22854.
  21. Lenore Cowen and Christopher G. Wagner. Compact roundtrip routing for digraphs. In Robert Endre Tarjan and Tandy J. Warnow, editors, Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17-19 January 1999, Baltimore, Maryland, USA, pages 885-886. ACM/SIAM, 1999. URL: http://dl.acm.org/citation.cfm?id=314500.315068.
  22. Tali Eilam-Tzoreff. The disjoint shortest paths problem. Discrete applied mathematics, 85(2):113-138, 1998. Google Scholar
  23. Michael Elkin and Ofer Neiman. Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC. In Christian Scheideler and Petra Berenbrink, editors, The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019, pages 333-341. ACM, 2019. URL: https://doi.org/10.1145/3323165.3323177.
  24. Shang-En Huang and Seth Pettie. Thorup-zwick emulators are universally optimal hopsets. Inf. Process. Lett., 142:9-13, 2019. URL: https://doi.org/10.1016/j.ipl.2018.10.001.
  25. Shang-En Huang and Seth Pettie. Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts. SIAM J. Discret. Math., 35(3):2129-2144, 2021. URL: https://doi.org/10.1137/19M1306154.
  26. Ken-ichi Kawarabayashi and Yusuke Kobayashi. Breaking o(n^1/2)-approximation algorithms for the edge-disjoint paths problem with congestion two. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 81-88. ACM, 2011. URL: https://doi.org/10.1145/1993636.1993648.
  27. Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Stephan Kreutzer. An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 70-78, 2014. Google Scholar
  28. Stavros G. Kolliopoulos and Clifford Stein. Approximating disjoint-path problems using greedy algorithms and packing integer programs. In Robert E. Bixby, E. Andrew Boyd, and Roger Z. Ríos-Mercado, editors, Integer Programming and Combinatorial Optimization, 6th International IPCO Conference, Houston, Texas, USA, June 22-24, 1998, Proceedings, volume 1412 of Lecture Notes in Computer Science, pages 153-168. Springer, 1998. URL: https://doi.org/10.1007/3-540-69346-7_12.
  29. Ilia Krasikov and Steven D. Noble. Finding next-to-shortest paths in a graph. Inf. Process. Lett., 92(3):117-119, 2004. URL: https://doi.org/10.1016/j.ipl.2004.06.020.
  30. William Lochet. A polynomial time algorithm for the k-disjoint shortest paths problem. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 169-178. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.12.
  31. Raul Lopes and Ignasi Sau. A relaxation of the directed disjoint paths problem: A global congestion metric helps. Theor. Comput. Sci., 898:75-91, 2022. URL: https://doi.org/10.1016/j.tcs.2021.10.023.
  32. Prabhakar Raghavan and Clark D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Comb., 7(4):365-374, 1987. URL: https://doi.org/10.1007/BF02579324.
  33. Liam Roditty, Mikkel Thorup, and Uri Zwick. Roundtrip spanners and roundtrip routing in directed graphs. ACM Trans. Algorithms, 4(3):29:1-29:17, 2008. URL: https://doi.org/10.1145/1367064.1367069.
  34. Aviad Rubinstein and Virginia Vassilevska Williams. SETH vs approximation. SIGACT News, 50(4):57-76, 2019. URL: https://doi.org/10.1145/3374857.3374870.
  35. Bang Ye Wu. A simpler and more efficient algorithm for the next-to-shortest path problem. In Weili Wu and Ovidiu Daescu, editors, Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part II, volume 6509 of Lecture Notes in Computer Science, pages 219-227. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-17461-2_18.
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