An SDP-based algorithm for linear-sized spectral sparsification

Yin Tat Lee, He Sun

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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ΤLGx ≤ xΤLHx ≤ (1 + ε)xΤLGx

holds for any xRn, where LG and LH 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 m1+Ω(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.
Original languageEnglish
Title of host publicationProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017
PublisherACM Association for Computing Machinery
Number of pages10
ISBN (Electronic)978-1-4503-4528-6
Publication statusPublished - 19 Jun 2017
Event49th Annual ACM SIGACT Symposium on Theory of Computing - Montreal, Canada
Duration: 19 Jun 201723 Jun 2017


Conference49th Annual ACM SIGACT Symposium on Theory of Computing
Abbreviated titleSTOC 2017


Dive into the research topics of 'An SDP-based algorithm for linear-sized spectral sparsification'. Together they form a unique fingerprint.

Cite this