Document Open Access Logo

Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs

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

PDF
Thumbnail PDF

File

LIPIcs.STACS.2020.25.pdf
  • Filesize: 0.7 MB
  • 14 pages

Document Identifiers

Author Details

Thomas Bläsius
  • Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
Philipp Fischbeck
  • Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
Tobias Friedrich
  • Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
Maximilian Katzmann
  • Hasso Plattner Institute, University of Potsdam, Potsdam, Germany

Funding

This research was partially funded by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG) - project number 390859508.

Cite As Get BibTex

Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, and Maximilian Katzmann. Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.STACS.2020.25

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Random network models
  • Mathematics of computing → Random graphs
Keywords
  • vertex cover
  • random graphs
  • hyperbolic geometry
  • efficient algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Takuya Akiba and Yoichi Iwata. Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover. Theor. Comput. Sci., 609:211-225, 2016. URL: https://doi.org/10.1016/j.tcs.2015.09.023.
  2. Alexandre Arenas, Albert-László Barabási, Vladimir Batagelj, Andrej Mrvar, Mark Newman, and Tore Opsahl. Gephi datasets. URL: https://github.com/gephi/gephi/wiki/Datasets.
  3. Vladimir Batagelj and Andrej Mrvar. Pajek datasets. http://vlado.fmf.uni-lj.si/pub/networks/data/, 2006. URL: http://vlado.fmf.uni-lj.si/pub/networks/data/.
  4. Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Hyperbolic Random Graphs: Separators and Treewidth. In 24th Annual European Symposium on Algorithms (ESA 2016), pages 15:1-15:16, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.15.
  5. Marián Boguná, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with hyperbolic mapping. Nat. Commun., 1:62, 2010. URL: https://doi.org/10.1038/ncomms1063.
  6. Liming Cai and David Juedes. On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci., 67:789-807, 2003. URL: https://doi.org/10.1016/S0022-0000(03)00074-6.
  7. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40):3736-3756, 2010. URL: https://doi.org/10.1016/j.tcs.2010.06.026.
  8. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  9. Mariana O. Da Silva, Gustavo A. Gimenez-Lugo, and Murilo V. G. Da Silva. Vertex cover in complex networks. Int. J. Mod. Phys. C, 24(11):1350078, 2013. URL: https://doi.org/10.1142/S0129183113500782.
  10. Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Ann. Math., 162(1):439-485, 2005. URL: https://doi.org/10.4007/annals.2005.162.439.
  11. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2012. Google Scholar
  12. Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. A measure & conquer approach for the analysis of exact algorithms. J. ACM, 56(5):25:1-25:32, 2009. URL: https://doi.org/10.1145/1552285.1552286.
  13. Tobias Friedrich and Anton Krohmer. On the diameter of hyperbolic random graphs. In Automata, Languages, and Programming, pages 614-625. Springer Berlin Heidelberg, 2015. URL: https://doi.org/10.1007/978-3-662-47666-6_49.
  14. Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random hyperbolic graphs: Degree sequence and clustering. In Automata, Languages, and Programming, pages 573-585. Springer Berlin Heidelberg, 2012. URL: https://doi.org/10.1007/978-3-642-31585-5_51.
  15. George Karakostas. A better approximation ratio for the vertex cover problem. ACM Trans. Algorithms, 5(4):41:1-41:8, 2009. URL: https://doi.org/10.1145/1597036.1597045.
  16. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε. J. Comput. Syst. Sci., 74(3):335-349, 2008. URL: https://doi.org/10.1016/j.jcss.2007.06.019.
  17. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Bogu~ná. Hyperbolic geometry of complex networks. Phys. Rev. E, 82:036106, 2010. URL: https://doi.org/10.1103/PhysRevE.82.036106.
  18. Jérôme Kunegis. KONECT: The koblenz network collection. In International Conference on World Wide Web (WWW), pages 1343-1350, 2013. URL: https://doi.org/10.1145/2487788.2488173.
  19. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, 2014. URL: http://snap.stanford.edu/data.
  20. Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015. URL: http://networkrepository.com.
  21. Hisao Tamaki, Hiromu Ohtsuka, Takuto Sato, and Keitaro Makii. TCS-Meiji PACE2017-TrackA. https://github.com/TCS-Meiji/PACE2017-TrackA, 2017. URL: https://github.com/TCS-Meiji/PACE2017-TrackA.
  22. Mingyu Xiao and Hiroshi Nagamochi. Exact algorithms for maximum independent set. Inf. Comput., 255:126-146, 2017. URL: https://doi.org/10.1016/j.ic.2017.06.001.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact