Skip to main content

Research Repository

Advanced Search

When can graph hyperbolicity be computed in linear time?

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

When can graph hyperbolicity be computed in linear time? Thumbnail


Authors

T. Fluschnik

C. Komusiewicz

A. Nichterlein

R. Niedermeier

N. Talmon



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 Mar 28, 2024
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

Files





You might also like



Downloadable Citations