When can graph hyperbolicity be computed in linear time?

Fluschnik, T.; Komusiewicz, C.; Mertzios, G.B.; Nichterlein, A.; Niedermeier, R.; Talmon, N.

Abstract

Hyperbolicity measures, in terms of (distance) metrics, how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unfortunately, the best known practical algorithms for computing the hyperbolicity number of a n-vertex graph have running time O(n4)O(n4) . Exploiting the framework of parameterized complexity analysis, we explore possibilities for “linear-time FPT” algorithms to compute hyperbolicity. For instance, we show that hyperbolicity can be computed in time 2O(k)+O(n+m)2O(k)+O(n+m) (m being the number of graph edges, k being the size of a vertex cover) while at the same time, unless the SETH fails, there is no 2o(k)n22o(k)n2 -time algorithm.

Citation

Fluschnik, T., Komusiewicz, C., Mertzios, G., Nichterlein, A., Niedermeier, R., & Talmon, N. (2023, July). When can graph hyperbolicity be computed in linear time?. Presented at Algorithms and Data Structures Symposium (WADS) 2017, St. John’s, NL, Canada

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Algorithms and Data Structures Symposium (WADS) 2017
• Start Date: Jul 31, 2023
• End Date: Aug 2, 2017
• Acceptance Date: Apr 14, 2017
• Online Publication Date: Jul 5, 2017
• Publication Date: Jul 5, 2017
• Deposit Date: Jun 26, 2017
• Publicly Available Date: Jul 5, 2018
• Print ISSN: 0302-9743
• Pages: 397-408
• Series Title: Lecture notes in computer science
• Series Number: 10389
• Series ISSN: 0302-9743,1611-3349
• Book Title: Algorithms and data structures : 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 – August 2, 2017 ; proceedings.
• ISBN: 9783319621265
• DOI: https://doi.org/10.1007/978-3-319-62127-2_34
• Public URL: https://durham-repository.worktribe.com/output/1146963