License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.20
URN: urn:nbn:de:0030-drops-146012
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14601/
Bläsius, Thomas ;
Friedrich, Tobias ;
Katzmann, Maximilian
Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry
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 tradeoff. On the one hand, it is known that it is NP-hard to approximate a minimum vertex cover within a factor of √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 close 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 + o(1))-approximation, asymptotically almost surely, and has a running time of ?(m log(n)).
The proposed algorithm is an adaption of the successful greedy approach, enhanced with a procedure that improves on parts of the graph where greedy is not optimal. This makes it possible to introduce a parameter that can be used to tune the tradeoff between approximation performance and running time. Our empirical evaluation on real-world networks shows that this allows for improving over the near-optimal results of the greedy approach.
BibTeX - Entry
@InProceedings{blasius_et_al:LIPIcs.ESA.2021.20,
author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Katzmann, Maximilian},
title = {{Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {20:1--20:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14601},
URN = {urn:nbn:de:0030-drops-146012},
doi = {10.4230/LIPIcs.ESA.2021.20},
annote = {Keywords: vertex cover, approximation, random graphs, hyperbolic geometry, efficient algorithm}
}
|
Keywords: |
|
vertex cover, approximation, random graphs, hyperbolic geometry, efficient algorithm |
|
Collection: |
|
29th Annual European Symposium on Algorithms (ESA 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
31.08.2021 |
