Document Open Access Logo

Faster Cut Sparsification of Weighted Graphs

Authors Sebastian Forster , Tijn de Vos

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.61.pdf
  • Filesize: 0.8 MB
  • 19 pages

Document Identifiers

Author Details

Sebastian Forster
  • Universität Salzburg, Austria
Tijn de Vos
  • Universität Salzburg, Austria

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 947702) and is supported by the Austrian Science Fund (FWF): P 32863-N.

Cite As Get BibTex

Sebastian Forster and Tijn de Vos. Faster Cut Sparsification of Weighted Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 61:1-61:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.61

Abstract

A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of (1±ε). This paper considers computing cut sparsifiers of weighted graphs of size O(nlog (n)/ε²). Our algorithm computes such a sparsifier in time O(m⋅min(α(n)log(m/n),log (n))), both for graphs with polynomially bounded and unbounded integer weights, where α(⋅) is the functional inverse of Ackermann’s function. This improves upon the state of the art by Benczúr and Karger (SICOMP 2015), which takes O(mlog² (n)) time. For unbounded weights, this directly gives the best known result for cut sparsification. Together with preprocessing by an algorithm of Fung et al. (SICOMP 2019), this also gives the best known result for polynomially-weighted graphs. Consequently, this implies the fastest approximate min-cut algorithm, both for graphs with polynomial and unbounded weights. In particular, we show that it is possible to adapt the state of the art algorithm of Fung et al. for unweighted graphs to weighted graphs, by letting the partial maximum spanning forest (MSF) packing take the place of the Nagamochi-Ibaraki (NI) forest packing. MSF packings have previously been used by Abraham at al. (FOCS 2016) in the dynamic setting, and are defined as follows: an M-partial MSF packing of G is a set ℱ = {F₁, … , F_M}, where F_i is a maximum spanning forest in G⧵ ⋃_{j = 1}^{i-1}F_j. Our method for computing (a sufficient estimation of) the MSF packing is the bottleneck in the running time of our sparsification algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
Keywords
  • Cut Sparsification
  • Graph Algorithms

Metrics

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

Related Versions

References

  1. Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In Proc. of the Symposium on Foundations of Computer Science (FOCS), pages 335-344, 2016. Google Scholar
  2. Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9(1):81-100, 1993. Google Scholar
  3. Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P Woodruff, and Qin Zhang. On sketching quadratic forms. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 311-319, 2016. Google Scholar
  4. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms, 30(4):532-563, 2007. URL: https://doi.org/10.1002/rsa.20130.
  5. Joshua Batson, Daniel A Spielman, and Nikhil Srivastava. Twice-ramanujan sparsifiers. SIAM Journal on Computing, 41(6):1704-1721, 2012. Google Scholar
  6. András A Benczúr and David R Karger. Approximating st minimum cuts in Õ (n²) time. In Proc. of the Symposium on Theory of Computing (STOC), pages 47-55, 1996. Google Scholar
  7. András A Benczúr and David R Karger. Randomized approximation schemes for cuts and flows in capacitated graphs. SIAM Journal on Computing, 44(2):290-319, 2015. Google Scholar
  8. Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23(4):493-507, 1952. Google Scholar
  9. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009. Google Scholar
  10. Michael Dinitz, Robert Krauthgamer, and Tal Wagner. Towards resistance sparsifiers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 40 of LIPIcs, pages 738-755, 2015. Google Scholar
  11. Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms, 15, July 2016. URL: https://doi.org/10.1145/3274651.
  12. Wai Shing Fung, Ramesh Hariharan, Nicholas J A Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. In Proc. of the Symposium on Theory of Computing (STOC), pages 71-80, New York, NY, USA, 2011. URL: https://doi.org/10.1145/1993636.1993647.
  13. Wai-Shing Fung, Ramesh Hariharan, Nicholas J A Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. SIAM Journal on Computing, 48(4):1196-1223, 2019. Google Scholar
  14. Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Minimum Cut in O(m log² n) Time. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, Proc. of the International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 57:1-57:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.57.
  15. Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. Faster algorithms for edge connectivity via random 2-out contractions. In Proc. of the Symposium on Discrete Algorithms (SODA), pages 1260-1279, 2020. Google Scholar
  16. Ramesh Hariharan and Debmalya Panigrahi. A general framework for graph sparsification, 2010. URL: http://arxiv.org/abs/1004.4080.
  17. David R Karger. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In Proc. of the Symposium on Discrete Algorithms (SODA), volume 93, pages 21-30, 1993. Google Scholar
  18. David R Karger. Random sampling in cut, flow, and network design problems. Mathematics of Operations Research, 24(2):383-413, 1999. Google Scholar
  19. David R Karger, Philip N Klein, and Robert E Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM, 42(2):321-328, 1995. Google Scholar
  20. David R Karger and Clifford Stein. A new approach to the minimum cut problem. Journal of the ACM, 43(4):601-640, 1996. Google Scholar
  21. Ioannis Koutis and Shen Chen Xu. Simple parallel and distributed algorithms for spectral graph sparsification. ACM Trans. Parallel Comput., 3(2):14:1-14:14, 2016. URL: https://doi.org/10.1145/2948062.
  22. Joseph B Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. of the American Mathematical Society, 7(1):48-50, 1956. Google Scholar
  23. Yin Tat Lee and He Sun. An sdp-based algorithm for linear-sized spectral sparsification. In Proc. of the Symposium on Theory of Computing (STOC), pages 678-687, 2017. Google Scholar
  24. Hiroshi Nagamochi and Toshihide Ibaraki. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics, 5(1):54-66, 1992. Google Scholar
  25. Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7(1-6):583-596, 1992. Google Scholar
  26. David Peleg and Alejandro A Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. Google Scholar
  27. Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913-1926, 2011. Google Scholar
  28. Daniel A Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40(4):981-1025, 2011. Google Scholar
  29. Robert E Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215-225, April 1975. URL: https://doi.org/10.1145/321879.321884.
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