Document Open Access Logo

Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity

Authors Max Franck , Sorrachai Yingchareonthawornchai

PDF
Thumbnail PDF

File

LIPIcs.SEA.2021.1.pdf
  • Filesize: 1.56 MB
  • 18 pages

Document Identifiers

Author Details

Max Franck
  • Department of Computer Science, Aalto University, Espoo, Finland
Sorrachai Yingchareonthawornchai
  • Department of Computer Science, Aalto University, Espoo, Finland

Funding

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

Cite As Get BibTex

Max Franck and Sorrachai Yingchareonthawornchai. Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SEA.2021.1

Abstract

Vertex connectivity is a well-studied concept in graph theory with numerous applications. A graph is k-connected if it remains connected after removing any k-1 vertices. The vertex connectivity of a graph is the maximum k such that the graph is k-connected. There is a long history of algorithmic development for efficiently computing vertex connectivity. Recently, two near linear-time algorithms for small k were introduced by [Forster et al. SODA 2020]. Prior to that, the best known algorithm was one by [Henzinger et al. FOCS'96] with quadratic running time when k is small.
In this paper, we study the practical performance of the algorithms by Forster et al. In addition, we introduce a new heuristic on a key subroutine called local cut detection, which we call degree counting. We prove that the new heuristic improves space-efficiency (which can be good for caching purposes) and allows the subroutine to terminate earlier. According to experimental results on random graphs with planted vertex cuts, random hyperbolic graphs, and real world graphs with vertex connectivity between 4 and 15, the degree counting heuristic offers a factor of 2-4 speedup over the original non-degree counting version for most of our data. It also outperforms the previous state-of-the-art algorithm by Henzinger et al. even on relatively small graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Algorithm Engineering
  • Algorithmic Graph Theory
  • Sublinear Algorithms

Metrics

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

Related Versions

Supplementary Materials

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google Scholar
  2. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. CoRR, abs/2010.05846, 2020. Google Scholar
  3. Deepayan Chakrabarti and Christos Faloutsos. Graph mining: Laws, generators, and algorithms. ACM Comput. Surv., 38(1):2, 2006. Google Scholar
  4. Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, and Nikos Parotsidis. Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs. In SODA, pages 1900-1918. SIAM, 2017. Google Scholar
  5. Chandra Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, and Clifford Stein. Experimental study of minimum cut algorithms. In SODA, pages 324-333. ACM/SIAM, 1997. Google Scholar
  6. Yefim Dinitz. Dinitz' algorithm: The original version and even’s version. In Essays in Memory of Shimon Even, volume 3895 of Lecture Notes in Computer Science, pages 218-240. Springer, 2006. Google Scholar
  7. Shimon Even. An algorithm for determining whether the connectivity of a graph is at least k. SIAM J. Comput., 4(3):393-396, 1975. Google Scholar
  8. Lester Randolph Ford and Delbert Ray Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8:399-404, 1956. Google Scholar
  9. Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms. In SODA, pages 2046-2065. SIAM, 2020. Google Scholar
  10. Harold N. Gabow. Using expander graphs to find vertex connectivity. J. ACM, 53(5):800-844, 2006. Google Scholar
  11. Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Deterministic graph cuts in subquadratic time: Sparse, balanced, and k-vertex. CoRR, abs/1910.07950, 2019. Google Scholar
  12. Loukas Georgiadis, Dionysios Kefallinos, Luigi Laura, and Nikos Parotsidis. An experimental study of algorithms for computing the edge connectivity of a directed graph. ALENEX, pages 85-97, 2021. Google Scholar
  13. Olivier Goldschmidt, Patrick Jaillet, and Richard Lasota. On reliability of graphs with node failures. Networks, 24(4):251-259, 1994. Google Scholar
  14. Monika Henzinger, Alexander Noe, Christian Schulz, and Darren Strash. Practical minimum cut algorithms. ACM J. Exp. Algorithmics, 23, 2018. Google Scholar
  15. Monika Rauch Henzinger, Satish Rao, and Harold N. Gabow. Computing vertex connectivity: New bounds from old techniques. In FOCS, pages 462-471. IEEE Computer Society, 1996. Google Scholar
  16. Michael Jünger, Giovanni Rinaldi, and Stefan Thienel. Practical performance of efficient minimum cut algorithms. Algorithmica, 26(1):172-195, 2000. Google Scholar
  17. D Kleitman. Methods for investigating connectivity of large graphs. IEEE Transactions on Circuit Theory, 16(2):232-233, 1969. Google Scholar
  18. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, 2014.
  19. Nathan Linial, László Lovász, and Avi Wigderson. Rubber bands, convex embeddings and graph connectivity. Comb., 8(1):91-102, 1988. Google Scholar
  20. Shaobin Liu, Kam-Hoi Cheng, and Xiaoping Liu. Network reliability with node failures. Networks, 35(2):109-117, 2000. Google Scholar
  21. Yang P. Liu and Aaron Sidford. Faster divergence maximization for faster maximum flow. CoRR, abs/2003.08929, 2020. Google Scholar
  22. Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7(5&6):583-596, 1992. Google Scholar
  23. Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Breaking quadratic time for small vertex connectivity and an approximation scheme. In STOC, pages 241-252. ACM, 2019. Google Scholar
  24. Manfred Padberg and Giovanni Rinaldi. An efficient algorithm for the minimum capacity cut problem. Math. Program., 47:19-36, 1990. Google Scholar
  25. Azzeddine Rigat. An experimental study of k-vertex connectivity algorithms. INFOCOMP, 11, 2012. Google Scholar
  26. Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. Networkit: A tool suite for large-scale complex network analysis. Netw. Sci., 4(4):508-530, 2016. Google Scholar
  27. Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. In FOCS, pages 919-930. IEEE, 2020. Google Scholar
  28. Moritz von Looz, Henning Meyerhenke, and Roman Prutkin. Generating random hyperbolic graphs in subquadratic time. In ISAAC, volume 9472 of Lecture Notes in Computer Science, pages 467-478. Springer, 2015. Google Scholar
  29. Douglas R. White and Frank Harary. The cohesiveness of blocks in social networks: Node connectivity and conditional density. Sociological Methodology, 31(1):305-359, 2001. 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