Abstract
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^{Τ}L_{G}x ≤ x^{Τ}L_{H}x ≤ (1 + ε)x^{Τ}L_{G}x
holds for any x ∈ R^{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 superlinear 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 twosided spectral sparsifier to a onesided spectral sparsifier; (3) constructing a onesided spectral sparsifier by a semidefinite program.
a (1 + ε)spectral sparsifier if
(1 − ε)x^{Τ}L_{G}x ≤ x^{Τ}L_{H}x ≤ (1 + ε)x^{Τ}L_{G}x
holds for any x ∈ R^{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 superlinear 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 twosided spectral sparsifier to a onesided spectral sparsifier; (3) constructing a onesided spectral sparsifier by a semidefinite program.
Original language  English 

Title of host publication  Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 1923, 2017 
Publisher  ACM Association for Computing Machinery 
Pages  678687 
Number of pages  10 
ISBN (Electronic)  9781450345286 
DOIs  
Publication status  Published  19 Jun 2017 
Event  49th Annual ACM SIGACT Symposium on Theory of Computing  Montreal, Canada Duration: 19 Jun 2017 → 23 Jun 2017 
Conference
Conference  49th Annual ACM SIGACT Symposium on Theory of Computing 

Abbreviated title  STOC 2017 
Country  Canada 
City  Montreal 
Period  19/06/17 → 23/06/17 
Fingerprint
Dive into the research topics of 'An SDPbased algorithm for linearsized spectral sparsification'. Together they form a unique fingerprint.Profiles

He Sun
 School of Informatics  Senior Lecturer in Algorithms and Complexity
 Laboratory for Foundations of Computer Science
 Data Science and Artificial Intelligence
Person: Academic: Research Active (Teaching)