An SDP-Based Algorithm for Linear-Sized Spectral Sparsification

Yin Tat Lee, He Sun

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+\epsilon )$-s…