Publication details for Dr George MertziosFluschnik, T., Komusiewicz, C., Mertzios, G.B., Nichterlein, A., Niedermeier, R. & Talmon, N. (2017), When can graph hyperbolicity be computed in linear time?, in Ellen, Faith, Kolokolova, Antonina & Sack, Jörg-Rüdiger eds, Lecture Notes in Computer Science, volume 10389 Algorithms and Data Structures Symposium (WADS). St. John’s, NL, Springer, Cham, 397-408.
- Publication type: Conference Paper
- ISSN/ISBN: 9783319621265, 9783319621272
- DOI: 10.1007/978-3-319-62127-2_34
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.