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

The problem of efficiently computing all kminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$k$document-edge-connected components (kminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$k$document-ECCs) of a graph G for a user-givenk has been extensively studied recently in view of its importance in many applications. The kminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$k$document-ECCs of G for all possible values ofk form a hierarchical structure; that is, any two different kminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$k$document-ECCs for the same k value are disjoint and any kminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$k$document-ECC is contained in a unique (k-1)minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$(k\text {-}1)$document-ECC. In this paper, we study the problem of efficiently constructing the hierarchy tree of the kminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$k$document-ECCs for all possible k values, for a graph G. The existing approaches TDminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\textsf{TD}$document and BUminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\textsf{BU}$document construct the hierarchy tree in either a top-down manner or a bottom-up manner, with both having the time complexity of O(δ(G)×TKECC(G))minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document${{\mathcal {O}}}\big (\delta (G)\times {\mathsf {T_{KECC}}} (G)\big )$document, where δ(G)minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\delta (G)$document is the degeneracy of G and TKECC(G)minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document${\mathsf {T_{KECC}}} (G)$document is the time complexity of computing all kminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$k$document-ECCs of G for a specific k value. Here, the degeneracy of G is defined as the maximum value among the minimum vertex degrees of all subgraphs of G and is at most mminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\sqrt{m}$document where m is the number of edges in G. To improve the time complexity, we propose a divide-and-conquer approach DCminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\textsf{DC}$document running in O((logδ(G))×TKECC(G))minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document${{\mathcal {O}}}\big ( (\log \delta (G))\times {\mathsf {T_{KECC}}} (G)\big )$document time; this time complexity is optimal up to a logarithmic factor. However, a straightforward implementation of DCminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\textsf{DC}$document would take O((m+n)logδ(G))minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document${{\mathcal {O}}}( (m + n) \log \delta (G))$document main-memory space, which could easily run out-of-memory when processing large graphs; here, n is the number of vertices in G. To reduce the main-memory footprint of our algorithm, we propose adjacency array-based techniques to optimize the space complexity to 2m+O(nlogδ(G))minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$2m+{{\mathcal {O}}}(n\log \delta (G))$document and denote our resulting algorithm by DC-AAminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {DC\text {-}AA}$document. As a by-product of DC-AAminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {DC\text {-}AA}$document, we also improve the space complexity of the state-of-the-art algorithm for computing all kminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$k$document-ECCs for a specific k to 2m+O(n)minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$2m + {{\mathcal {O}}}(n)$document, by using the same technique as used in DC-AAminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {DC\text {-}AA}$document. Finally, we propose optimization techniques to improve the practical efficiency of the existing approach BUminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\textsf{BU}$document and denote the space-optimized version of it as BU∗-AAminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {BU^*\text {-}AA}$document which runs in O(δ(G)×TKECC(G))minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document${{\mathcal {O}}}\big (\delta (G)\times {\mathsf {T_{KECC}}} (G)\big )$document time and 2m+O(n)minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$2m+{{\mathcal {O}}}(n)$document space. Extensive experiments on large real graphs and synthetic graphs demonstrate that our algorithms DC-AAminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathsf {DC\text {-}AA}$document and BU∗-AAminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek