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+ε)-spectral sparsifier if (1-ε) x T L G x ≤ x T L H x ≤(1+ε) x T L G x holds for any x Εℝ n , where L G and L H are the respective Laplacian matrices of G and H . Noticing that Ω( m ) time is needed for any algorithm to construct a spectral sparsifier and a spectral sparsifier of G requires Ω( n ) edges, a natural question is to investigate, for any constant ε, if a (1+ε)-spectral sparsifier of G with O ( n ) edges can be constructed in Ο( m ) time, where the Ο notation suppresses polylogarithmic factors. All previous constructions on spectral sparsification require either super-linear number of edges or m 1+Ω(1) time. In this work we answer this question affirmatively by presenting an algorithm that, for any undirected graph G and ε>0, outputs a (1+ε)-spectral sparsifier of G with O ( n /ε 2 ) edges in Ο( m /ε O (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.

Authors

• Yin Tat Lee
• He Sun 0001

Keywords

• spectral graph theory
• spectral sparsification