When can Graph Hyperbolicity be computed in Linear Time?

2017/02/21 by Fluschnik, Till, Komusiewicz, Christian, Mertzios, George B. +3
#05C12 #68Q17 #68Q25 #68R10 #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2

paper · doi:10.48550/arxiv.1702.06503

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⁴), 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²-time algorithm.

Related

• Fast approximation of centrality and distances in hyperbolic graphs
• Enumeration of Far-Apart Pairs by Decreasing Distance for Faster\n Hyperbolicity Computation
• Shedding Light on Problems with Hyperbolic Graph Learning
• Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring
• On the Hyperbolicity of Small-World and Tree-Like Random Graphs