Fluschnik, T. and Komusiewicz, C. and Mertzios, G.B. and Nichterlein, A. and Niedermeier, R. and Talmon, N. (2019) 'When can graph hyperbolicity be computed in linear time?', Algorithmica., 81 (5). pp. 2016-2045.
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 .
|Full text:||(AM) Accepted Manuscript|
Download PDF (523Kb)
|Publisher Web site:||https://doi.org/10.1007/s00453-018-0522-6|
|Publisher statement:||This is a post-peer-review, pre-copyedit version of an article published in Algorithmica. The final authenticated version is available online at: https://doi.org/10.1007/s00453-018-0522-6|
|Date accepted:||03 October 2018|
|Date deposited:||24 September 2018|
|Date of first online publication:||13 October 2018|
|Date first made open access:||13 October 2019|
Save or Share this output
|Look up in GoogleScholar|