License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.25
URN: urn:nbn:de:0030-drops-118865
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11886/
Go to the corresponding LIPIcs Volume Portal

Bläsius, Thomas ; Fischbeck, Philipp ; Friedrich, Tobias ; Katzmann, Maximilian

Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs

pdf-format:
LIPIcs-STACS-2020-25.pdf (0.7 MB)

Abstract

The VertexCover problem is proven to be computationally hard in different ways: It is NP-complete to find an optimal solution and even 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. Similarly, greedy algorithms deliver very good approximations to the optimal solution in practice.
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. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that, on real instances, this leads to better approximations than the standard greedy approach within reasonable time.

BibTeX - Entry

@InProceedings{blsius_et_al:LIPIcs:2020:11886,
  author =	{Thomas Bl{\"a}sius and Philipp Fischbeck and Tobias Friedrich and Maximilian Katzmann},
  title =	{{Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Christophe Paul and Markus Bl{\"a}ser},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11886},
  URN =		{urn:nbn:de:0030-drops-118865},
  doi =		{10.4230/LIPIcs.STACS.2020.25},
  annote =	{Keywords: vertex cover, random graphs, hyperbolic geometry, efficient algorithm}
}

Keywords: vertex cover, random graphs, hyperbolic geometry, efficient algorithm
Collection: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Issue Date: 2020
Date of publication: 04.03.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI