KIT | KIT-Bibliothek | Impressum | Datenschutz

Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry

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

Abstract:

Finding a minimum vertex cover in a network is a fundamental NP-complete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of an algorithm (allowing non-optimal outputs) for an improved running time. For the vertex cover problem, there is a gap between theory and practice when it comes to understanding this trade-off. On the one hand, it is known that it is NP-hard to approximate a minimum vertex cover within a factor of $\sqrt{2}$. On the other hand, a simple greedy algorithm yields close to optimal approximations in practice. A promising approach towards understanding this discrepancy is to recognize the differences between theoretical worst-case instances and real-world networks. Following this direction, we narrow the gap between theory and practice by providing an algorithm that efficiently computes nearly optimal vertex cover approximations on hyperbolic random graphs; a network model that closely resembles real-world networks in terms of degree distribution, clustering, and the small-world property. More precisely, our algorithm computes a (1+𝑜(1))-approximation, asymptotically almost surely, and has a running time of ${\mathcal {O}}(m \log (n))$. ... mehr


Verlagsausgabe §
DOI: 10.5445/IR/1000160583
Veröffentlicht am 13.07.2023
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2023
Sprache Englisch
Identifikator ISSN: 0178-4617, 1432-0541
KITopen-ID: 1000160583
Erschienen in Algorithmica
Verlag Springer
Vorab online veröffentlicht am 27.06.2023
Nachgewiesen in Dimensions
Web of Science
Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page