Document Open Access Logo

Faster Cut-Equivalent Trees in Simple Graphs

Author Tianyi Zhang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.109.pdf
  • Filesize: 0.85 MB
  • 18 pages

Document Identifiers

Author Details

Tianyi Zhang
  • Tel Aviv University, Israel

Funding

This publication has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 803118 UncertainENV).

Acknowledgements

The author would like to thank helpful discussions with Prof. Ran Duan and Dr. Amir Abboud.

Cite As Get BibTex

Tianyi Zhang. Faster Cut-Equivalent Trees in Simple Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 109:1-109:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.109

Abstract

Let G = (V, E) be an undirected connected simple graph on n vertices. A cut-equivalent tree of G is an edge-weighted tree on the same vertex set V, such that for any pair of vertices s, t ∈ V, the minimum (s, t)-cut in the tree is also a minimum (s, t)-cut in G, and these two cuts have the same cut value. In a recent paper [Abboud, Krauthgamer and Trabelsi, STOC 2021], the authors propose the first subcubic time algorithm for constructing a cut-equivalent tree. More specifically, their algorithm has Õ(n^{2.5}) running time. Later on, this running time was significantly improved to n^{2+o(1)} by two independent works [Abboud, Krauthgamer and Trabelsi, FOCS 2021] and [Li, Panigrahi, Saranurak, FOCS 2021], and then to (m+n^{1.9})^{1+o(1)} by [Abboud, Krauthgamer and Trabelsi, SODA 2022].
In this paper, we improve the running time to Õ(n²) graphs if near-linear time max-flow algorithms exist, or Õ(n^{17/8}) using the currently fastest max-flow algorithm. Although our algorithm is slower than previous works, the runtime bound becomes better by a sub-polynomial factor in dense simple graphs when assuming near-linear time max-flow algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • graph algorithms
  • minimum cuts
  • max-flow

Metrics

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

Related Versions

References

  1. Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi. Gomory-hu tree in subcubic time. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.04958.
  2. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. New algorithms and lower bounds for all-pairs max-flow in undirected graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 48-61. SIAM, 2020. Google Scholar
  3. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Subcubic algorithms for gomory-hu tree in unweighted graphs. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.10281.
  4. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Apmf< apsp? gomory-hu tree for unweighted graphs in almost-quadratic time. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.02981.
  5. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Friendly cut sparsifiers and faster gomory-hu trees. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3630-3649. SIAM, 2022. Google Scholar
  6. Jan van den Brand, Yin Tat Lee, Yang P Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and 𝓁₁-regression in nearly linear time for dense instances. arXiv preprint, 2021. URL: http://arxiv.org/abs/2101.05719.
  7. Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Optimization—Eureka, You Shrink!, pages 11-26. Springer, 2003. Google Scholar
  8. Harold N Gabow. Applications of a poset representation to edge connectivity and graph rigidity. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pages 812-821. IEEE Computer Society, 1991. Google Scholar
  9. Harold N Gabow. A matroid approach to finding edge connectivity and packing arborescences. Journal of Computer and System Sciences, 50(2):259-273, 1995. Google Scholar
  10. Ralph E Gomory and Tien Chung Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551-570, 1961. Google Scholar
  11. Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan. The expander hierarchy and its applications to dynamic graph algorithms. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2212-2228. SIAM, 2021. Google Scholar
  12. Frieda Granot and Refael Hassin. Multi-terminal maximum flows in node-capacitated networks. Discrete applied mathematics, 13(2-3):157-163, 1986. Google Scholar
  13. Dan Gusfield. Very simple methods for all pairs network flow analysis. SIAM Journal on Computing, 19(1):143-155, 1990. Google Scholar
  14. Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi, and Anand Bhalgat. An o(mn) gomory-hu tree construction algorithm for unweighted graphs. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 605-614, 2007. Google Scholar
  15. Tarun Kathuria, Yang P Liu, and Aaron Sidford. Unit capacity maxflow in almost m^4/3 time. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 119-130. IEEE, 2020. Google Scholar
  16. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in Õ(√rank) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 424-433. IEEE, 2014. Google Scholar
  17. Jason Li and Debmalya Panigrahi. Deterministic min-cut in poly-logarithmic max-flows. In Annual Symposium on Foundations of Computer Science, 2020. Google Scholar
  18. Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak. A nearly optimal all-pairs min-cuts algorithm in simple graphs. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.02233.
  19. Yang P Liu and Aaron Sidford. Faster energy maximization for faster maximum flow. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 803-814, 2020. Google Scholar
  20. Aleksander Madry. Computing maximum flow with augmenting electrical flows. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 593-602. IEEE, 2016. Google Scholar
  21. Tianyi Zhang. Gomory-hu trees in quadratic time. arXiv preprint, 2021. URL: http://arxiv.org/abs/2112.01042.
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