Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

4 Downloads (Pure)

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.

Original languageEnglish
Title of host publication19th International Symposium on Experimental Algorithms, SEA 2021
EditorsDavid Coudert, Emanuele Natale
Pages1:1-1:18
ISBN (Electronic)978-3-95977-185-6
DOIs
Publication statusPublished - 1 Jun 2021
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Experimental Algorithms - Nice, France
Duration: 7 Jun 20219 Jun 2021

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume190
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Symposium on Experimental Algorithms
Abbreviated titleSEA
CountryFrance
CityNice
Period07/06/202109/06/2021

Fingerprint

Dive into the research topics of 'Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity'. Together they form a unique fingerprint.

Cite this