Abstract
Finding a minimum vertex cover in a network is a fundamental NPcomplete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of an algorithm (allowing nonoptimal 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 NPhard 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 worstcase instances and realworld 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 realworld networks in terms of degree distribution, clustering, and the smallworld 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 realworld networks shows that this allows for improving over the nearoptimal 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 ScaleFree Networks with Underlying Hyperbolic Geometry}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {20:120:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14601},
URN = {urn:nbn:de:0030drops146012},
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 