Probabilistic Spectral Sparsification In Sublinear Time

الأصل · EN

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ᶜ) with an 1±ε multiplicative error and a δ|S| additive error. We show how to produce a probabilistic (ε,δ)-spectral sparsifier with O(n 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³/²⁺ᵗ) time O(√ n/t)-approximation algorithm for the sparsest cut problem and the balanced separator problem. - A n¹⁺ᵒ⁽¹⁾/ε⁴ time approximation minimum s-t cut algorithm with an ε n additive error.