Subgraph sparsification and nearly optimal ultrasparsifiers

Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang Hua Teng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 W k such that G+W k 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.

Original languageEnglish (US)
Title of host publicationSTOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing
Pages57-65
Number of pages9
DOIs
StatePublished - Jul 23 2010
Event42nd ACM Symposium on Theory of Computing, STOC 2010 - Cambridge, MA, United States
Duration: Jun 5 2010Jun 8 2010

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other42nd ACM Symposium on Theory of Computing, STOC 2010
CountryUnited States
CityCambridge, MA
Period6/5/106/8/10

Keywords

  • algebraic connectivity
  • approximation algorithms
  • graph sparsification
  • ultrasparsifiers

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Subgraph sparsification and nearly optimal ultrasparsifiers'. Together they form a unique fingerprint.

  • Cite this

    Kolla, A., Makarychev, Y., Saberi, A., & Teng, S. H. (2010). Subgraph sparsification and nearly optimal ultrasparsifiers. In STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing (pp. 57-65). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1806689.1806699