Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

2015/08/13 by Lee, Yin Tat, Sun, He · 4 citations
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1508.03261

Abstract

We present the first almost-linear time algorithm for constructing linear-sized spectral sparsification for graphs. This improves all previous constructions of linear-sized spectral sparsification, which requires Ω(n²) time. A key ingredient in our algorithm is a novel combination of two techniques used in literature for constructing spectral sparsification: Random sampling by effective resistance, and adaptive constructions based on barrier functions.

Cited by

• Hedgegraph Polymatroids
• Efficient Algorithms for Partitioning Circulant Graphs with Optimal Spectral Approximation
• Online Sparsification of Bipartite-Like Clusters in Graphs
• Taxonomy of reduction matrices for Graph Coarsening

Related

• Spectral Sparsification of Graphs
• Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
• A Framework for Analyzing Resparsification Algorithms
• An SDP-Based Algorithm for Linear-Sized Spectral Sparsification
• Probabilistic Spectral Sparsification In Sublinear Time