A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition

Download PDF

Abstract

Driven by applications in graph analytics, the problem of efficiently computing all k-edge connected components (k-ECCs) of a graph G for a user-given k has been extensively and well studied. It is known that the k-ECCs of G for all possible values of k form a hierarchical structure. In this paper, we study the problem of efficiently constructing the hierarchy tree for G which compactly encodes the k-ECCs for all possible k values in space linear to the number of vertices n. All existing approaches construct the hierarchy tree in $O(\delta(G)\times T_{KECC}(G) )$ time, where $\delta(G)$ is the degeneracy of G and $T_{KECC}(G)$ is the time complexity of computing all k-ECCs of G for a specific k value. To improve the time complexity, we propose a divide-and-conquer approach running in $O( (\log\delta(G))\times T_{KECC}(G))$ time, which is optimal up to a logarithmic factor. However, a straightforward implementation of our algorithm would result in a space complexity of $O( (m + n) \log \delta(G))$. As main memory also becomes a scarce resource when processing large-scale graphs, we further propose techniques to optimize the space complexity to $2m+O(n\log \delta(G))$, where m is the number of edges in G. Extensive experiments on large real graphs and synthetic graphs demonstrate that our approach outperforms the state-of-the-art approaches by up to 28 times in terms of running time, and by up to 8 times in terms of main memory usage. As a by-product, we also improve the space complexity of computing all k-ECCs for a specific k to $2m + O(n)$.