Document Open Access Logo

Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry

Authors Thomas Bläsius, Tobias Friedrich , Maximilian Katzmann

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2021.20.pdf
  • Filesize: 0.92 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

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

Metrics

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

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.

Cite As Get BibTex

Thomas Bläsius, Tobias Friedrich, and Maximilian Katzmann. Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.20

Author Details

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

Funding

This research was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Grant No. 390859508.

References

  1. Faisal N. Abu-Khzam, Rebecca L. Collins, Michael R. Fellows, Michael A. Langston, W. Henry Suters, and Christopher T. Symons. Kernelization algorithms for the vertex cover problem: Theory and experiments. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, pages 62-69, 2004. Google Scholar
  2. 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.
  3. Eric Angel, Romain Campigotto, and Christian Laforest. Implementation and comparison of heuristics for the vertex cover problem on huge graphs. In Experimental Algorithms, pages 39-50, 2012. Google Scholar
  4. Yonatan Bilu and Nathan Linial. Are stable instances easy? Comb. Probab. Comput., 21(5):643–660, 2012. URL: https://doi.org/10.1017/S0963548312000193.
  5. 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), pages 25:1-25:14, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.25.
  6. Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, and Marianne Thieffry. Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pages 20:1-20:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.20.
  7. Thomas Bläsius, Tobias Friedrich, and Maximilian Katzmann. Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry. CoRR, abs/2010.02787, 2020. URL: https://arxiv.org/abs/2010.02787.
  8. Marián Boguná, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with hyperbolic mapping. Nature Communications, 1:62, 2010. URL: https://doi.org/10.1038/ncomms1063.
  9. Vaggos Chatziafratis, Tim Roughgarden, and Jan Vondrak. Stability and Recovery for Independence Systems. In 25th Annual European Symposium on Algorithms (ESA 2017), pages 26:1-26:15, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.26.
  10. Ankit Chauhan, Tobias Friedrich, and Ralf Rothenberger. Greed is Good for Deterministic Scale-Free Networks. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), pages 33:1-33:15, 2016. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2016.33.
  11. 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.
  12. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2012. Google Scholar
  13. Leah Epstein, Asaf Levin, and Gerhard J. Woeginger. Vertex cover meets scheduling. Algorithmica, 74:1148–1173, 2016. URL: https://doi.org/10.1007/s00453-015-9992-y.
  14. Eric Filiol, Edouard Franc, Alessandro Gubbioli, Benoit Moquet, and Guillaume Roblot. Combinatorial optimisation of worm propagation on an unknown network. International Journal of Computer, Electrical, Automation, Control and Information Engineering, 1:2931-2937, 2007. Google Scholar
  15. Guillermo García-Pérez, Marián Boguñá, Antoine Allard, and M. Serrano. The hidden hyperbolic geometry of international trade: World trade atlas 1870–2013. Scientific Reports, 6:33441, 2016. URL: https://doi.org/10.1038/srep33441.
  16. Mikael Gast and Mathias Hauptmann. Approximability of the vertex cover problem in power-law graphs. Theoretical Computer Science, 516:60-70, 2014. URL: https://doi.org/10.1016/j.tcs.2013.11.004.
  17. 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.
  18. 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.
  19. Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a Symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. Google Scholar
  20. 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.
  21. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Phys. Rev. E, 82:036106, 2010. URL: https://doi.org/10.1103/PhysRevE.82.036106.
  22. Anton Krohmer. Structures & algorithms in Hyperbolic Random Graphs. doctoralthesis, University of Potsdam, 2016. Google Scholar
  23. Frosso S. Makri, Andreas N. Philippou, and Zaharias M. Psillakis. Success run statistics defined on an urn model. Advances in Applied Probability, 39(4):991–1019, 2007. URL: https://doi.org/10.1239/aap/1198177236.
  24. Tobias Müller and Merlijn Staps. The diameter of KPKVB random graphs. Advances in Applied Probability, 51:358–377, 2019. URL: https://doi.org/10.1017/apr.2019.23.
  25. Kihong Park and Walter Williger. The Internet As a Large-Scale Complex System. Oxford University Press, Inc., 2005. Google Scholar
  26. K. Subhash, D. Minzer, and M. Safra. Pseudorandom sets in grassmann graph have near-perfect expansion. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 592-601, 2018. Google Scholar
  27. Kevin Verbeek and Subhash Suri. Metric embedding, hyperbolic space, and social networks. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SOCG'14, page 501–510, 2014. URL: https://doi.org/10.1145/2582112.2582139.
  28. André L. Vignatti and Murilo V.G. da Silva. Minimum vertex cover in generalized random graphs with power law degree distribution. Theoretical Computer Science, 647:101–111, 2016. URL: https://doi.org/10.1016/j.tcs.2016.08.002.
  29. Lutz Warnke. On the method of typical bounded differences. Combinatorics, Probability and Computing, 25(2):269–299, 2016. URL: https://doi.org/10.1017/S0963548315000103.
  30. 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.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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