TY - GEN

T1 - Subgraph sparsification and nearly optimal ultrasparsifiers

AU - Kolla, Alexandra

AU - Makarychev, Yury

AU - Saberi, Amin

AU - Teng, Shang Hua

PY - 2010

Y1 - 2010

N2 - We consider a variation of the spectral sparsification problem where we are required to keep a subgraph of the original graph. Formally, given a union of two weighted graphs G and W and an integer k, we are asked to find a k-edge weighted graph Wk such that G+Wk is a good spectral sparsifer of G+W. We will refer to this problem as the subgraph (spectral) sparsification. We present a nontrivial condition on G and W such that a good sparsifier exists and give a polynomial-time algorithm to find the sparsifer. As an application of our technique, we show that for each positive integer k, every n-vertex weighted graph has an (n-1+k)-edge spectral sparsifier with relative condition number at most n/k log n, Õ(log log n) where Õ() hides lower order terms. Our bound nearly settles a question left open by Spielman and Teng about ultrasparsifiers. We also present another application of our technique to spectral optimization in which the goal is to maximize the algebraic connectivity of a graph (e.g. turn it into an expander) with a limited number of edges.

AB - We consider a variation of the spectral sparsification problem where we are required to keep a subgraph of the original graph. Formally, given a union of two weighted graphs G and W and an integer k, we are asked to find a k-edge weighted graph Wk such that G+Wk is a good spectral sparsifer of G+W. We will refer to this problem as the subgraph (spectral) sparsification. We present a nontrivial condition on G and W such that a good sparsifier exists and give a polynomial-time algorithm to find the sparsifer. As an application of our technique, we show that for each positive integer k, every n-vertex weighted graph has an (n-1+k)-edge spectral sparsifier with relative condition number at most n/k log n, Õ(log log n) where Õ() hides lower order terms. Our bound nearly settles a question left open by Spielman and Teng about ultrasparsifiers. We also present another application of our technique to spectral optimization in which the goal is to maximize the algebraic connectivity of a graph (e.g. turn it into an expander) with a limited number of edges.

KW - algebraic connectivity

KW - approximation algorithms

KW - graph sparsification

KW - ultrasparsifiers

UR - http://www.scopus.com/inward/record.url?scp=77954719315&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954719315&partnerID=8YFLogxK

U2 - 10.1145/1806689.1806699

DO - 10.1145/1806689.1806699

M3 - Conference contribution

AN - SCOPUS:77954719315

SN - 9781605588179

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 57

EP - 65

BT - STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing

T2 - 42nd ACM Symposium on Theory of Computing, STOC 2010

Y2 - 5 June 2010 through 8 June 2010

ER -