Publication details for Dr George MertziosFluschnik, T., Komusiewicz, C., Mertzios, G.B., Nichterlein, A., Niedermeier, R. & Talmon, N. (2019). When can graph hyperbolicity be computed in linear time? Algorithmica 81(5): 2016–2045.
- Publication type: Journal Article
- ISSN/ISBN: 0178-4617, 1432-0541
- DOI: 10.1007/s00453-018-0522-6
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
Hyperbolicity is a distance-based measure of 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 algorithms used in practice for computing the hyperbolicity number of an n-vertex graph have running time O(n4) . Exploiting the framework of parameterized complexity analysis, we explore possibilities for “linear-time FPT” algorithms to compute hyperbolicity. For example, we show that hyperbolicity can be computed in 2O(k)+O(n+m) time (where m and k denote the number of edges and the size of a vertex cover in the input graph, respectively) while at the same time, unless the Strong Exponential Time Hypothesis (SETH) fails, there is no 2o(k)⋅n2−ε -time algorithm for every ε>0 .