Document Open Access Logo

Finding the KT Partition of a Weighted Graph in Near-Linear Time

Authors Simon Apers, Paweł Gawrychowski, Troy Lee

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.32.pdf
  • Filesize: 0.67 MB
  • 14 pages

Document Identifiers

Author Details

Simon Apers
  • CNRS and IRIF, Paris, France
Paweł Gawrychowski
  • Institute of Computer Science, University of Wrocław, Poland
Troy Lee
  • Centre for Quantum Software and Information, University of Technology Sydney, Australia

Funding

  • Gawrychowski, Paweł: Partially supported by the Bekker programme of the Polish National Agency for Academic Exchange (PPN/BEK/2020/1/00444).
  • Lee, Troy: Supported in part by the Australian Research Council Grant No: DP200100950.

Cite As Get BibTex

Simon Apers, Paweł Gawrychowski, and Troy Lee. Finding the KT Partition of a Weighted Graph in Near-Linear Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.32

Abstract

In a breakthrough work, Kawarabayashi and Thorup (J. ACM'19) gave a near-linear time deterministic algorithm to compute the weight of a minimum cut in a simple graph G = (V,E). A key component of this algorithm is finding the (1+ε)-KT partition of G, the coarsest partition {P_1, …, P_k} of V such that for every non-trivial (1+ε)-near minimum cut with sides {S, ̄{S}} it holds that P_i is contained in either S or  ̄{S}, for i = 1, …, k. In this work we give a near-linear time randomized algorithm to find the (1+ε)-KT partition of a weighted graph. Our algorithm is quite different from that of Kawarabayashi and Thorup and builds on Karger’s framework of tree-respecting cuts (J. ACM'00).
We describe a number of applications of the algorithm. (i) The algorithm makes progress towards a more efficient algorithm for constructing the polygon representation of the set of near-minimum cuts in a graph. This is a generalization of the cactus representation, and was initially described by Benczúr (FOCS'95). (ii) We improve the time complexity of a recent quantum algorithm for minimum cut in a simple graph in the adjacency list model from Õ(n^{3/2}) to Õ(√{mn}), when the graph has n vertices and m edges. (iii) We describe a new type of randomized algorithm for minimum cut in simple graphs with complexity 𝒪(m + n log⁶ n). For graphs that are not too sparse, this matches the complexity of the current best 𝒪(m + n log² n) algorithm which uses a different approach based on random contractions.
The key technical contribution of our work is the following. Given a weighted graph G with m edges and a spanning tree T of G, consider the graph H whose nodes are the edges of T, and where there is an edge between two nodes of H iff the corresponding 2-respecting cut of T is a non-trivial near-minimum cut of G. We give a 𝒪(m log⁴ n) time deterministic algorithm to compute a spanning forest of H.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Graph theory

Metrics

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

Related Versions

References

  1. Simon Apers, Paweł Gawrychowski, and Troy Lee. Finding the KT partition of a weighted graph in near-linear time. CoRR, abs/2111.01378, 2021. URL: http://arxiv.org/abs/2111.01378.
  2. Simon Apers and Troy Lee. Quantum complexity of minimum cut. In Proceedings of the 36th Computational Complexity Conference (CCC '21), pages 28:1-28:3. LIPIcs, 2021. Google Scholar
  3. András Benczúr. Cut structures and randomized algorithms in edge-connectivity problems. PhD thesis, MIT, 1997. Google Scholar
  4. András A. Benczúr. A representation of cuts within 6/5 times the edge connectivity with applications. In Proceedings of 36th Annual Symposium on Foundations of Computer Science (FOCS '95), pages 92-102. IEEE Computer Society, 1995. URL: https://doi.org/10.1109/SFCS.1995.492466.
  5. András A. Benczúr and Michel X. Goemans. Deformable polygon representation and near-mincuts. In Martin Grötschel, Gyula O. H. Katona, and Gábor Sági, editors, Building Bridges: Between Mathematics and Computer Science, pages 103-135. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. URL: https://doi.org/10.1007/978-3-540-85221-6_3.
  6. Michael A. Bender and Martin Farach-Colton. The LCA problem revisited. In Proceedings of 4th Latin American Symposium on Theoretical Informatics (LATIN '00), pages 88-94. Springer, 2000. Google Scholar
  7. Efim A Dinitz, Alexander V Karzanov, and Michael V Lomonosov. On the structure of the system of minimum edge cuts in a graph. Issledovaniya po Diskretnoi Optimizatsii (Studies in Discrete Optimization), pages 290-306, 1976. Appeared in Russian. Google Scholar
  8. Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. Journal of Computer and System Sciences, 50(2):259-273, 1995. URL: https://doi.org/10.1006/jcss.1995.1022.
  9. Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Minimum cut in O(mlog² n) time. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP '20), volume 168 of LIPIcs, pages 57:1-57:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  10. Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. Faster algorithms for edge connectivity via random 2-out contractions. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA '20), pages 1260-1279. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.77.
  11. Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. A randomized rounding approach to the traveling salesman problem. In 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS '11), pages 550-559. IEEE, 2011. Google Scholar
  12. Ralph E. Gomory and Te C. Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551-570, 1961. URL: http://www.jstor.org/stable/2098881.
  13. Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338-355, 1984. Google Scholar
  14. Monika Henzinger, Satish Rao, and Di Wang. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing, 49(1):1-36, 2020. URL: https://doi.org/10.1137/18M1180335.
  15. David R. Karger. Minimum cuts in near-linear time. Journal of the ACM, 47(1):46-76, 2000. Announced at STOC 1996. Google Scholar
  16. David R. Karger and Debmalya Panigrahi. A near-linear time algorithm for constructing a cactus representation of minimum cuts. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), pages 246-255. SIAM, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496798.
  17. Anna R Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric TSP. In 53rd Annual ACM-SIGACT Symposium on Theory of Computing (STOC '21), pages 32-45, 2021. Google Scholar
  18. Ken-ichi Kawarabayashi and Mikkel Thorup. Deterministic edge connectivity in near-linear time. Journal of the ACM, 66(1):4:1-4:50, 2019. Announced at STOC 2015. URL: https://doi.org/10.1145/3274663.
  19. Jason Li. Deterministic mincut in almost-linear time. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC '21), pages 384-395. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451114.
  20. On-Hei S. Lo, Jens M. Schmidt, and Mikkel Thorup. Compact cactus representations of all non-trivial min-cuts. Discrete Applied Mathematics, 303:296-304, 2020. URL: https://doi.org/10.1016/j.dam.2020.03.046.
  21. Sagnik Mukhopadhyay and Danupon Nanongkai. Weighted min-cut: sequential, cut-query, and streaming algorithms. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC '20), pages 496-509. ACM, 2020. Google Scholar
  22. Jaroslav Nesetril, Eva Milková, and Helena Nesetrilová. Otakar Borůvka on the minimum spanning tree problem: Translation of both the 1926 papers, comments, history. Discrete Mathematics, 233(1-3):3-36, 2001. URL: https://doi.org/10.1016/S0012-365X(00)00224-7.
  23. Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg. Computing exact minimum cuts without knowing the graph. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS '18), pages 39:1-39:16. LIPIcs, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.39.
  24. Daniel D Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, 1983. 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