Document Open Access Logo

Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems

Author Adam Karczmarz

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.83.pdf
  • Filesize: 0.79 MB
  • 20 pages

Document Identifiers

Author Details

Adam Karczmarz
  • Institute of Informatics, University of Warsaw, Poland

Funding

  • Karczmarz, Adam: supported by ERC Consolidator Grant 772346 TUgbOAT and by the Foundation for Polish Science (FNP) via the START programme.

Cite As Get BibTex

Adam Karczmarz. Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 83:1-83:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.83

Abstract

We consider the directed minimum weight cycle problem in the fully dynamic setting. To the best of our knowledge, so far no fully dynamic algorithms have been designed specifically for the minimum weight cycle problem in general digraphs. One can achieve Õ(n²) amortized update time by simply invoking the fully dynamic APSP algorithm of Demetrescu and Italiano [J. ACM '04]. This bound, however, yields no improvement over the trivial recompute-from-scratch algorithm for sparse graphs.
Our first contribution is a very simple deterministic (1+ε)-approximate algorithm supporting vertex updates (i.e., changing all edges incident to a specified vertex) in conditionally near-optimal Õ(mlog{(W)}/ε) amortized time for digraphs with real edge weights in [1,W]. Using known techniques, the algorithm can be implemented on planar graphs and also gives some new sublinear fully dynamic algorithms maintaining approximate cuts and flows in planar digraphs.
Additionally, we show a Monte Carlo randomized exact fully dynamic minimum weight cycle algorithm with Õ(mn^{2/3}) worst-case update that works for real edge weights. To this end, we generalize the exact fully dynamic APSP data structure of Abraham et al. [SODA'17] to solve the multiple-pairs shortest paths problem, where one is interested in computing distances for some k (instead of all n²) fixed source-target pairs after each update. We show that in such a scenario, Õ((m+k)n^{2/3}) worst-case update time is possible.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Shortest paths
Keywords
  • Dynamic graph algorithms
  • minimum weight cycle
  • dynamic shortest paths

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. Ittai Abraham, Shiri Chechik, and Sebastian Krinninger. Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 440-452, 2017. URL: https://doi.org/10.1137/1.9781611974782.28.
  3. Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. Algorithms and hardness for diameter in dynamic graphs. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 13:1-13:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.13.
  4. Giorgio Ausiello, Giuseppe F. Italiano, Alberto Marchetti-Spaccamela, and Umberto Nanni. Incremental algorithms for minimal length paths. J. Algorithms, 12(4):615-638, 1991. URL: https://doi.org/10.1016/0196-6774(91)90036-X.
  5. Surender Baswana, Ramesh Hariharan, and Sandeep Sen. Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. J. Algorithms, 62(2):74-92, 2007. URL: https://doi.org/10.1016/j.jalgor.2004.08.004.
  6. Aaron Bernstein. Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 693-702. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/FOCS.2009.16.
  7. Aaron Bernstein. Maintaining shortest paths under deletions in weighted directed graphs. SIAM J. Comput., 45(2):548-574, 2016. URL: https://doi.org/10.1137/130938670.
  8. Aaron Bernstein and Liam Roditty. Improved dynamic algorithms for maintaining approximate shortest paths under deletions. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1355-1365. SIAM, 2011. URL: https://doi.org/10.1137/1.9781611973082.104.
  9. Glencora Borradaile and Philip N. Klein. An O(n log n) algorithm for maximum st-flow in a directed planar graph. J. ACM, 56(2):9:1-9:30, 2009. URL: https://doi.org/10.1145/1502793.1502798.
  10. Karl Bringmann, Marvin Künnemann, and Karol Wegrzycki. Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 943-954. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316373.
  11. Panagiotis Charalampopoulos and Adam Karczmarz. Single-source shortest paths and strong connectivity in dynamic planar graphs. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 31:1-31:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.31.
  12. Shiri Chechik. Near-optimal approximate decremental all pairs shortest paths. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 170-181. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00025.
  13. Shiri Chechik and Gur Lifshitz. Optimal girth approximation for dense directed graphs. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 290-300. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.19.
  14. Shiri Chechik, Yang P. Liu, Omer Rotem, and Aaron Sidford. Constant girth approximation for directed graphs in subquadratic time. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1010-1023. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384330.
  15. Julia Chuzhoy and Thatchaphol Saranurak. Deterministic algorithms for decremental shortest paths via layered core decomposition. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2478-2496. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.147.
  16. Marek Cygan, Harold N. Gabow, and Piotr Sankowski. Algorithmic applications of baur-strassen’s theorem: Shortest cycles, diameter, and matchings. J. ACM, 62(4):28:1-28:30, 2015. URL: https://doi.org/10.1145/2736283.
  17. Mina Dalirrooyfard and Virginia Vassilevska Williams. Conditionally optimal approximation algorithms for the girth of a directed graph. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 35:1-35:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.35.
  18. Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths. J. ACM, 51(6):968-992, 2004. URL: https://doi.org/10.1145/1039488.1039492.
  19. Jeff Erickson. Maximum flows and parametric shortest paths in planar graphs. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 794-804. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.65.
  20. Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen. Decremental APSP in directed graphs versus an adaptive adversary. CoRR, abs/2010.00937, 2020. URL: http://arxiv.org/abs/2010.00937.
  21. Jittat Fakcharoenphol and Satish Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci., 72(5):868-889, 2006. URL: https://doi.org/10.1016/j.jcss.2005.05.007.
  22. Harold N. Gabow. Scaling algorithms for network problems. J. Comput. Syst. Sci., 31(2):148-168, 1985. URL: https://doi.org/10.1016/0022-0000(85)90039-X.
  23. Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Deterministic algorithms for decremental approximate shortest paths: Faster and simpler. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 2522-2541. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.154.
  24. Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Fully-dynamic all-pairs shortest paths: Improved worst-case time and space bounds. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 2562-2574. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.156.
  25. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM J. Comput., 45(3):947-1006, 2016. URL: https://doi.org/10.1137/140957299.
  26. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  27. Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph. SIAM J. Comput., 7(4):413-423, 1978. URL: https://doi.org/10.1137/0207033.
  28. Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, pages 313-322, 2011. URL: https://doi.org/10.1145/1993636.1993679.
  29. Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. J. ACM, 24(1):1-13, 1977. URL: https://doi.org/10.1145/321992.321993.
  30. Donald B. Johnson. Parallel algorithms for minimum cuts and maximum flows in planar networks. J. ACM, 34(4):950-967, 1987. URL: https://doi.org/10.1145/31846.31849.
  31. Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir. Submatrix maximum queries in monge matrices and partial monge matrices, and their applications. ACM Trans. Algorithms, 13(2):26:1-26:42, 2017. URL: https://doi.org/10.1145/3039873.
  32. Adam Karczmarz and Jakub Lacki. Simple label-correcting algorithms for partially dynamic approximate shortest paths in directed graphs. In 3rd Symposium on Simplicity in Algorithms, SOSA@SODA 2020, pages 106-120. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976014.15.
  33. Adam Karczmarz and Jakub Łącki. Reliable hubs for partially-dynamic all-pairs shortest paths in directed graphs. In 27th Annual European Symposium on Algorithms, ESA 2019, pages 65:1-65:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.65.
  34. Philip N. Klein. Multiple-source shortest paths in planar graphs. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pages 146-155, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070454.
  35. Hung-Chun Liang and Hsueh-I Lu. Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths. SIAM J. Discret. Math., 31(1):454-476, 2017. URL: https://doi.org/10.1137/16M1057152.
  36. Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1236-1252. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.80.
  37. Jakub Łącki and Piotr Sankowski. Min-cuts and shortest cycles in planar graphs in o(n loglogn) time. In Camil Demetrescu and Magnús M. Halldórsson, editors, Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings, volume 6942 of Lecture Notes in Computer Science, pages 155-166. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-23719-5_14.
  38. Shay Mozes, Kirill Nikolaev, Yahav Nussbaum, and Oren Weimann. Minimum cut of directed planar graphs in O(n log log n) time. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 477-494. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.32.
  39. Yahav Nussbaum. Network flow problems in planar graphs. PhD thesis, Tel Aviv University, 2014. Google Scholar
  40. James B. Orlin and Antonio Sedeño-Noda. An O(nm) time algorithm for finding the min length directed cycle in a graph. 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 1866-1879. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.122.
  41. Seth Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci., 312(1):47-74, 2004. URL: https://doi.org/10.1016/S0304-3975(03)00402-X.
  42. Liam Roditty and Virginia Vassilevska Williams. Minimum weight cycles and triangles: Equivalences and algorithms. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 180-189. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.27.
  43. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. Algorithmica, 61(2):389-401, 2011. URL: https://doi.org/10.1007/s00453-010-9401-5.
  44. Liam Roditty and Uri Zwick. Dynamic approximate all-pairs shortest paths in undirected graphs. SIAM J. Comput., 41(3):670-683, 2012. URL: https://doi.org/10.1137/090776573.
  45. Mikkel Thorup. Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Proceedings, pages 384-396, 2004. URL: https://doi.org/10.1007/978-3-540-27810-8_33.
  46. Mikkel Thorup. Worst-case update times for fully-dynamic all-pairs shortest paths. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC 2005, pages 112-119, 2005. URL: https://doi.org/10.1145/1060590.1060607.
  47. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. J. ACM, 65(5):27:1-27:38, 2018. URL: https://doi.org/10.1145/3186893.
  48. Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289-317, 2002. URL: https://doi.org/10.1145/567112.567114.
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