Probabilistic Spectral Sparsification In Sublinear Time

Abstract

In this paper, we introduce a variant of spectral sparsification, called probabilistic $(\epsilon ,\delta )$-spectral sparsification. Roughly speaking, it preserves the cut value of any cut $(S,S^c)$ with an $1\pm \epsilon$ multiplicative error and a $\delta \left|S\right|$ additive error. We show how to produce a probabilistic $(\epsilon ,\delta )$-spectral sparsifier with $O(n\log n/{\epsilon }^2)$ edges in time $\tilde{O}(n/{\epsilon }^2\delta )$ 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)}/{\epsilon }^4$ time approximation minimum s-t cut algorithm with an $\epsilon n$ additive error.

References in corpus (2)

• Single pass sparsification in the streaming model with edge deletions
• Graph Sparsification via Refinement Sampling