Expander decomposition and pruning: faster, stronger, and simpler

DOI10.1137/1.9781611975482.162zbMATH Open1430.68238arXiv1812.08958OpenAlexW2903365982MaRDI QIDQ5236352FDOQ5236352

Authors:

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We study the problem of graph clustering where the goal is to partition a graph into clusters, i.e. disjoint subsets of vertices, such that each cluster is well connected internally while sparsely connected to the rest of the graph. In particular, we use a natural bicriteria notion motivated by Kannan, Vempala, and Vetta which we refer to as {em expander decomposition}. Expander decomposition has become one of the building blocks in the design of fast graph algorithms, most notably in the nearly linear time Laplacian solver by Spielman and Teng, and it also has wide applications in practice. We design algorithm for the parametrized version of expander decomposition, where given a graph $G$ of $m$ edges and a parameter $phi$, our algorithm finds a partition of the vertices into clusters such that each cluster induces a subgraph of conductance at least $phi$ (i.e. a $phi$ expander), and only a $widetildeO(phi)$ fraction of the edges in $G$ have endpoints across different clusters. Our algorithm runs in $widetildeO(m/phi)$ time, and is the first nearly linear time algorithm when $phi$ is at least $1/lo{g}^{O(1)}m$, which is the case in most practical settings and theoretical applications. Previous results either take $Omega(m^{1+o(1)})$ time, or attain nearly linear time but with a weaker expansion guarantee where each output cluster is guaranteed to be contained inside some unknown $phi$ expander. Our result achieve both nearly linear running time and the strong expander guarantee for clusters. Moreover, a main technique we develop for our result can be applied to obtain a much better emph{expander pruning} algorithm, which is the key tool for maintaining an expander decomposition on dynamic graphs. Finally, we note that our algorithm is developed from first principles based on relatively simple and basic techniques, thus making it very likely to be practical.

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

Recommendations

• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Spectral sparsification of graphs
• Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition
• Expander flows, geometric embeddings and graph partitioning

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Cited In (8)

• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Local flow partitioning for faster edge connectivity
• Near-optimal Distributed Triangle Enumeration via Expander Decompositions
• Dulmage-Mendelsohn canonical decomposition as a generic pruning technique
• Faster connectivity in low-rank hypergraphs via expander decomposition
• Finding a small vertex cut on distributed networks
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast

This page was built for publication: Expander decomposition and pruning: faster, stronger, and simpler

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