2026-07-22T01:18:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14601 2024-03-06T10:54:24Z ddc:004 open_access

Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry Bläsius, Thomas Friedrich, Tobias Katzmann, Maximilian vertex cover approximation random graphs hyperbolic geometry efficient algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Bläsius and Tobias Friedrich and Maximilian Katzmann 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.20 urn:nbn:de:0030-drops-146012 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.20 eng https://creativecommons.org/licenses/by/4.0/legalcode