Probabilistic Spectral Sparsification In Sublinear Time

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,Sc) with an 1±varepsilon multiplicative error and a δleft|Sright| additive error. We show how to produce a probabilistic (varepsilon,δ)-spectral sparsifier with O(nlog n/varepsilon2) edges in time tildeO(n/varepsilon2δ) time for unweighted undirected graph. This gives fastest known sub-linear time algorithms for different cut problems on unweighted undirected graph such as - An tildeO(n/OPT+n3/2+t) time O(√log n/t)-approximation algorithm for the sparsest cut problem and the balanced separator problem. - A n1+o(1)/varepsilon4 time approximation minimum s-t cut algorithm with an varepsilon n additive error.