Title: An SDP-Based Algorithm for Linear-Sized Spectral Sparsification,
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+\varepsilon)$-spectral sparsifier if \[
(1-\varepsilon)x^{\intercal}L_Gx\leq x^{\intercal} L_{H} x\leq (1+\varepsilon)
x^{\intercal} L_Gx \] holds for any $x\in\mathbb{R}^n$, where $L_G$ and $L_{H}$
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 $\tilde{O}(m)$ time,
where the $\tilde{O}$ notation suppresses polylogarithmic factors. All previous
constructions on spectral sparsification require either super-linear number of
edges or $m^{1+\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/\varepsilon^2)$ edges in
$\tilde{O}(m/\varepsilon^{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.