KIT | KIT-Bibliothek | Impressum | Datenschutz

Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs

Bläsius, Thomas ORCID iD icon 1; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, Maximilian
1 Karlsruher Institut für Technologie (KIT)


The computational complexity of the VERTEXCOVER problem has been studied extensively. Most notably, it is NP-complete to find an optimal solution and typically NP-hard to find an approximation with reasonable factors. In contrast, recent experiments suggest that on many real-world networks the run time to solve VERTEXCOVER is way smaller than even the best known FPT-approaches can explain. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VERTEXCOVER problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice.

Verlagsausgabe §
DOI: 10.5445/IR/1000139769
Veröffentlicht am 12.11.2021
DOI: 10.1007/s00224-021-10062-9
Zitationen: 2
Web of Science
Zitationen: 1
Zitationen: 2
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2023
Sprache Englisch
Identifikator ISSN: 1432-4350, 0025-5661, 1433-0490
KITopen-ID: 1000139769
Erschienen in Theory of Computing Systems
Verlag Springer
Band 67
Seiten 28-51
Vorab online veröffentlicht am 28.10.2021
Nachgewiesen in Scopus
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page