When can graph hyperbolicity be computed in linear time?

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

Abstract

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 .

Citation

Fluschnik, T., Komusiewicz, C., Mertzios, G., Nichterlein, A., Niedermeier, R., & Talmon, N. (2019). When can graph hyperbolicity be computed in linear time?. Algorithmica, 81(5), 2016-2045. https://doi.org/10.1007/s00453-018-0522-6

• Journal Article Type: Article
• Acceptance Date: Oct 3, 2018
• Online Publication Date: Oct 13, 2018
• Publication Date: May 31, 2019
• Deposit Date: Sep 23, 2018
• Publicly Available Date: Oct 13, 2019
• Journal: Algorithmica
• Print ISSN: 0178-4617
• Electronic ISSN: 1432-0541
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 81
• Issue: 5
• Pages: 2016-2045
• DOI: https://doi.org/10.1007/s00453-018-0522-6
• Public URL: https://durham-repository.worktribe.com/output/1313777