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+ε)-spectral sparsifier if