Probabilistic Spectral Sparsification In Sublinear Time

2013/12/31 by Lee, Yin Tat
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1401.0085

Abstract

In this paper, we introduce a variant of spectral sparsification, called probabilistic (ε,δ)-spectral sparsification. Roughly speaking, it preserves the cut value of any cut (S,S^c) with an 1±ε multiplicative error and a δ|S| additive error. We show how to produce a probabilistic (ε,δ)-spectral sparsifier with O(nlog n/ε²) edges in time O(n/ε²δ) time for unweighted undirected graph. This gives fastest known sub-linear time algorithms for different cut problems on unweighted undirected graph such as - An O(n/OPT+n^3/2+t) time O(√(log n/t))-approximation algorithm for the sparsest cut problem and the balanced separator problem. - A n^1+o(1)/ε⁴ time approximation minimum s-t cut algorithm with an ε n additive error.

Related

• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
• An SDP-Based Algorithm for Linear-Sized Spectral Sparsification
• A Framework for Analyzing Resparsification Algorithms
• Spectral Sparsification of Graphs
• Spectral Subspace Sparsification