{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:29Z","timestamp":1759638989028,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hasso-Plattner-Institut f\u00fcr Digital Engineering gGmbH"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The computational complexity of the <jats:sc>VertexCover<\/jats:sc> problem has been studied extensively. Most notably, it is NP-complete to find an optimal solution and typically 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 <jats:sc>VertexCover<\/jats:sc> is way smaller than even the best known FPT-approaches can explain. 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 <jats:sc>VertexCover<\/jats:sc> 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.<\/jats:p>","DOI":"10.1007\/s00224-021-10062-9","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T02:02:26Z","timestamp":1635386546000},"page":"28-51","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs"],"prefix":"10.1007","volume":"67","author":[{"given":"Thomas","family":"Bl\u00e4sius","sequence":"first","affiliation":[]},{"given":"Philipp","family":"Fischbeck","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0076-6308","authenticated-orcid":false,"given":"Tobias","family":"Friedrich","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9302-5527","authenticated-orcid":false,"given":"Maximilian","family":"Katzmann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"key":"10062_CR1","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2015.09.023","volume":"609","author":"T Akiba","year":"2016","unstructured":"Akiba, T., Iwata, Y.: Branch-and-Reduce Exponential\/FPT Algorithms in Practice: A Case Study of Vertex Cover. Theor. Comput. Sci. 609, 211\u2013225 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2015.09.023","journal-title":"Theor. Comput. Sci."},{"issue":"21","key":"10062_CR2","doi-asserted-by":"publisher","first-page":"4947","DOI":"10.1242\/jcs.02714","volume":"118","author":"R Albert","year":"2005","unstructured":"Albert, R.: Scale-Free networks in cell biology. J. Cell Sci. 118 (21), 4947\u20134957 (2005). https:\/\/doi.org\/10.1242\/jcs.02714","journal-title":"J. Cell Sci."},{"key":"10062_CR3","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","volume":"74","author":"R Albert","year":"2002","unstructured":"Albert, R., Barab\u00e1si, A.L.: Statistical Mechanics of Complex Networks. Rev. Mod. Phys. 74, 47\u201397 (2002). https:\/\/doi.org\/10.1103\/RevModPhys.74.47","journal-title":"Rev. Mod. Phys."},{"key":"10062_CR4","unstructured":"Arenas, A., Barab\u00e1si, A.L., Batagelj, V., Mrvar, A., Newman, M., Opsahl, T.: Gephi Datasets. https:\/\/github.com\/gephi\/gephi\/wiki\/Datasets"},{"key":"10062_CR5","unstructured":"Batagelj, V., Mrvar, A.: Pajek datasets. http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/data\/ (2006)"},{"key":"10062_CR6","doi-asserted-by":"publisher","unstructured":"Bla\u0307sius, T., Fischbeck, P., Friedrich, T.: Katzmann, M.: Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs. In: 37Th International Symposium on Theoretical Aspects of Computer Science, STACS. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.25, pp 25:1\u201325:14. Montpellier, France (2020)","DOI":"10.4230\/LIPIcs.STACS.2020.25"},{"key":"10062_CR7","doi-asserted-by":"publisher","unstructured":"Bl\u00e4sius, T., Freiberger, C., Friedrich, T., Katzmann, M., Montenegro-Retana, F.: Thieffry, M.: Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. In: 45Th International Colloquium on Automata, Languages, and Programming (ICALP), pp 20:1\u201320:14 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.20","DOI":"10.4230\/LIPIcs.ICALP.2018.20"},{"key":"10062_CR8","unstructured":"Bl\u00e4sius, T., Friedrich, T., Katzmann, M.: Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry. To appear in the proceedings of the 29th Annual European Symposium on Algorithms (ESA) (2021)"},{"key":"10062_CR9","doi-asserted-by":"publisher","unstructured":"Bl\u00e4sius, T., Friedrich, T., Krohmer, A.: Hyperbolic Random Graphs: Separators and Treewidth. In: 24Th Annual European Symposium on Algorithms (ESA), pp 15:1\u201315:16 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.15","DOI":"10.4230\/LIPIcs.ESA.2016.15"},{"key":"10062_CR10","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1038\/ncomms1063","volume":"1","author":"M Bogun\u00e1","year":"2010","unstructured":"Bogun\u00e1, M., Papadopoulos, F., Krioukov, D.: Sustaining the Internet with Hyperbolic Mapping. Nat. Commun. 1, 62 (2010). https:\/\/doi.org\/10.1038\/ncomms1063","journal-title":"Nat. Commun."},{"key":"10062_CR11","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L Cai","year":"2003","unstructured":"Cai, L., Juedes, D.: On the Existence of Subexponential Parameterized Algorithms. J. Comput. Syst. Sci. 67, 789\u2013807 (2003). https:\/\/doi.org\/10.1016\/S0022-0000(03)00074-6","journal-title":"J. Comput. Syst. Sci."},{"issue":"40","key":"10062_CR12","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I. A., Xia, G.: Improved Upper Bounds for Vertex Cover. Theor. Comput. Sci. 411(40), 3736\u20133756 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2010.06.026","journal-title":"Theor. Comput. Sci."},{"key":"10062_CR13","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F. V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"10062_CR14","doi-asserted-by":"publisher","unstructured":"Dorogovtsev, S.: Lectures on Complex Networks. Oxford University Press, Inc. https:\/\/doi.org\/10.1093\/acprof:oso\/9780199548927.001.0001 (2010)","DOI":"10.1093\/acprof:oso\/9780199548927.001.0001"},{"key":"10062_CR15","unstructured":"Dubhashi, D. P., Panconesi, A: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press (2012)"},{"issue":"5","key":"10062_CR16","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"FV Fomin","year":"2009","unstructured":"Fomin, F. V., Grandoni, F., Kratsch, D.: A Measure & Conquer Approach for the Analysis of Exact Algorithms. J. ACM 56(5), 25:1\u201325:32 (2009). https:\/\/doi.org\/10.1145\/1552285.1552286","journal-title":"J. ACM"},{"issue":"2","key":"10062_CR17","doi-asserted-by":"publisher","first-page":"1314","DOI":"10.1137\/17M1123961","volume":"32","author":"T Friedrich","year":"2018","unstructured":"Friedrich, T., Krohmer, A.: On the Diameter of Hyperbolic Random Graphs. SIAM J. Discret. Math. 32(2), 1314\u20131334 (2018). https:\/\/doi.org\/10.1137\/17M1123961","journal-title":"SIAM J. Discret. Math."},{"key":"10062_CR18","doi-asserted-by":"publisher","unstructured":"Gugelmann, L., Panagiotou, K., Peter, U.: Random Hyperbolic Graphs: Degree Sequence and Clustering. In: Automata, Languages, and Programming, pp. 573 \u2013 585. Springer Berlin Heidelberg. https:\/\/doi.org\/10.1007\/978-3-642-31585-5_51 (2012)","DOI":"10.1007\/978-3-642-31585-5_51"},{"key":"10062_CR19","doi-asserted-by":"publisher","unstructured":"Kiwi, M. A., Mitsche, D: A Bound for the Diameter of Random Hyperbolic Graphs. In: Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, ANALCO. https:\/\/doi.org\/10.1137\/1.9781611973761.3, pp 26\u201339. SIAM (2015)","DOI":"10.1137\/1.9781611973761.3"},{"key":"10062_CR20","doi-asserted-by":"publisher","first-page":"036106","DOI":"10.1103\/PhysRevE.82.036106","volume":"82","author":"D Krioukov","year":"2010","unstructured":"Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., Bogu\u00f1\u00e1, M.: Hyperbolic Geometry of Complex Networks. Phys. Rev. E 82, 036106 (2010). https:\/\/doi.org\/10.1103\/PhysRevE.82.036106","journal-title":"Phys. Rev. E"},{"key":"10062_CR21","doi-asserted-by":"publisher","unstructured":"Kunegis, J.: KONECT: The Koblenz Network Collection. In: International Conference on World Wide Web (WWW), Pp. 1343 \u2013 1350. https:\/\/doi.org\/10.1145\/2487788.2488173 (2013)","DOI":"10.1145\/2487788.2488173"},{"key":"10062_CR22","unstructured":"Leskovec, J., Krevl, A.: SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data (2014)"},{"key":"10062_CR23","doi-asserted-by":"publisher","unstructured":"Ramsay, A., Richtmyer, R.D.: Introduction to Hyperbolic Geometry. Springer. https:\/\/doi.org\/10.1007\/978-1-4757-5585-5 (1995)","DOI":"10.1007\/978-1-4757-5585-5"},{"key":"10062_CR24","doi-asserted-by":"crossref","unstructured":"Rossi, R.A., Ahmed, N.K.: The Network Data Repository with Interactive Graph Analytics and Visualization. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. http:\/\/networkrepository.com (2015)","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"10062_CR25","unstructured":"Tamaki, H., Ohtsuka, H., Sato, T., Makii, K.: TCS-meiji PACE2017-tracka github.com\/TCS-meiji\/PACE2017-tracka (2017)"},{"key":"10062_CR26","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","volume":"255","author":"M Xiao","year":"2017","unstructured":"Xiao, M., Nagamochi, H.: Exact Algorithms for Maximum Independent Set. Inf. Comput. 255, 126\u2013146 (2017). https:\/\/doi.org\/10.1016\/j.ic.2017.06.001","journal-title":"Inf. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10062-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-021-10062-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10062-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,14]],"date-time":"2023-02-14T08:07:27Z","timestamp":1676362047000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-021-10062-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,28]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["10062"],"URL":"https:\/\/doi.org\/10.1007\/s00224-021-10062-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2021,10,28]]},"assertion":[{"value":"13 September 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}