An SDP-Based Algorithm for Linear-Sized Spectral Sparsification

For any undirected and weighted graph G=(V,E,w) with n vertices and m edges, we call a sparse subgraph H of G, with proper reweighting of the edges, a (1+varepsilon)-spectral sparsifier if [ (1-varepsilon)xintercalLGx≤ xintercal LH x≤ (1+varepsilon) xintercal LGx ] holds for any x∈ℝn, where LG and LH are the respective Laplacian matrices of G and H. Noticing that Omega(m) time is needed for any algorithm to construct a spectral sparsifier and a spectral sparsifier of G requires Omega(n) edges, a natural question is to investigate, for any constant varepsilon, if a (1+varepsilon)-spectral sparsifier of G with O(n) edges can be constructed in tildeO(m) time, where the tildeO notation suppresses polylogarithmic factors. All previous constructions on spectral sparsification require either super-linear number of edges or m1+Omega(1) time. In this work we answer this question affirmatively by presenting an algorithm that, for any undirected graph G and varepsilon>0, outputs a (1+varepsilon)-spectral sparsifier of G with O(n/varepsilon2) edges in tildeO(m/varepsilonO(1)) time. Our algorithm is based on three novel techniques: (1) a new potential function which is much easier to compute yet has similar guarantees as the potential functions used in previous references; (2) an efficient reduction from a two-sided spectral sparsifier to a one-sided spectral sparsifier; (3) constructing a one-sided spectral sparsifier by a semi-definite program.