When can graph hyperbolicity be computed in linear time?

DOI10.1007/978-3-319-62127-2_34zbMATH Open1491.68143DBLPconf/wads/FluschnikKMNNT17arXiv1702.06503OpenAlexW2592125861WikidataQ62039063 ScholiaQ62039063MaRDI QIDQ5920105FDOQ5920105

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)

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.

Full work available at URL: https://arxiv.org/abs/1702.06503

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

Mathematics Subject Classification ID

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

Cited In (12)

• Fast approximation and exact computation of negative curvature parameters of graphs
• Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
• 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
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• On computing the hyperbolicity of real-world graphs
• On adaptive algorithms for maximum matching
• Computing graph hyperbolicity using dominating sets
• On computing the Gromov hyperbolicity
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Enumeration of Far-apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation

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)