When can graph hyperbolicity be computed in linear time?

DOI10.1007/978-3-319-62127-2_34MaRDI QIDQ5920105zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Till Fluschnik, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, Nimrod Talmon

Publication date 22 September 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.06503, http://dro.dur.ac.uk/22111/1/22111.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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 algorithms for computing the hyperbolicity number of a graph (the smaller, the more tree-like) have running time $O(n^4)$, where $n$ is the number of graph vertices. 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 $O(2^{O(k)}+n+m)$ ($m$ being the number of graph edges) while at the same time, unless the SETH fails, there is no $2^{o(k)}{n}^2$-time algorithm.

Recommendations

• When can graph hyperbolicity be computed in linear time?
• Applying clique-decomposition for computing Gromov hyperbolicity
• On computing the hyperbolicity of real-world graphs
• On computing the Gromov hyperbolicity
• Fast approximation and exact computation of negative curvature parameters of graphs

Cited in

(13)

• Fast approximation of centrality and distances in hyperbolic graphs
• Applying clique-decomposition for computing Gromov hyperbolicity
• Fast approximation and exact computation of negative curvature parameters of graphs
• On computing the Gromov hyperbolicity
• On computing the hyperbolicity of real-world graphs
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
• On adaptive algorithms for maximum matching
• Fast approximation and exact computation of negative curvature parameters of graphs
• When can graph hyperbolicity be computed in linear time?
• Enumeration of Far-apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation
• Computing graph hyperbolicity using dominating sets

This page was built for publication: When can graph hyperbolicity be computed in linear time?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5920105)