Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Kelner, Jonathan A.; Levin, Alex http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-30332
URL:

;

Spectral Sparsification in the Semi-Streaming Setting

pdf-format:


Abstract

Let G be a graph with n vertices and m edges. A sparsifier of G is a sparse graph on the same vertex set approximating $G$ in some natural way. It allows us to say useful things about $G$ while considering much fewer than m edges. The strongest commonly-used notion of sparsification is spectral sparsification; H is a spectral sparsifier of G if the quadratic forms induced by the Laplacians of G and H approximate one another well. This notion is strictly stronger than the earlier concept of combinatorial sparsification. In this paper, we consider a semi-streaming setting, where we have only ~O(n) storage space, and we thus cannot keep all of G. In this case, maintaining a sparsifier instead gives us a useful approximation to G, allowing us to answer certain questions about the original graph without storing all of it. In this paper, we introduce an algorithm for constructing a spectral sparsifier of G with O(n log n/epsilon^2) edges (where epsilon is a parameter measuring the quality of the sparsifier), taking ~O(m) time and requiring only one pass over G. In addition, our algorithm has the property that it maintains at all times a valid sparsifier for the subgraph of G that we have received. Our algorithm is natural and conceptually simple. As we read edges of $G,$ we add them to the sparsifier $H$. Whenever $H$ gets too big, we resparsify it in $tilde O(n)$ time. Adding edges to a graph changes the structure of its sparsifier's restriction to the already existing edges. It would thus seem that the above procedure would cause errors to compound each time that we resparsify, and that we should need to either retain significantly more information or reexamine previously discarded edges in order to construct the new sparsifier. However, we show how to use the information contained in $H$ to perform this resparsification using only the edges retained by earlier steps in nearly linear time.

BibTeX - Entry

@InProceedings{kelner_et_al:LIPIcs:2011:3033,
  author =	{Jonathan A. Kelner and Alex Levin},
  title =	{{Spectral Sparsification in the Semi-Streaming Setting}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{440--451},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3033},
  URN =		{urn:nbn:de:0030-drops-30332},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2011.440},
  annote =	{Keywords: algorithms and data structures,  graph algorithms, spectral graph theory, sub-linear space algorithms, spectral sparsification}
}

Keywords: algorithms and data structures, graph algorithms, spectral graph theory, sub-linear space algorithms, spectral sparsification
Seminar: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue date: 2011
Date of publication: 2011


DROPS-Home | Fulltext Search | Imprint Published by LZI