Probabilistic Spectral Sparsification In Sublinear Time
Yin Tat Lee · arXiv (Cornell University) · 2013
In this paper, we introduce a variant of spectral sparsification, called probabilistic $(\varepsilon,δ)$-spectral sparsification. Roughly speaking, it preserves the cut value of any cut $(S,S^{c})$ with an $1\pm\varepsilon$ multiplicative error and a $δ\left|S\right|$ additive error. We show how to produce a probabilistic $(\varepsilon,δ)$-spectral sparsifier with $O(n\log n/\varepsilon^{2})$ edges in time $\tilde{O}(n/\varepsilon^{2}δ)$ time for unweighted undirected graph. This gives fastest known sub-linear time algorithms for different cut problems on unweighted undirected graph such as - An $\tilde{O}(n/OPT+n^{3/2+t})$ time $O(\sqrt{\log n/t})$-approximation algorithm for the sparsest cut problem and the balanced separator problem. - A $n^{1+o(1)}/\varepsilon^{4}$ time approximation minimum s-t cut algorithm with an $\varepsilon n$ additive error.