License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.18
URN: urn:nbn:de:0030-drops-62801
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6280/
Go to the corresponding LIPIcs Volume Portal

Huang, Zengfeng ; Peng, Pan

Dynamic Graph Stream Algorithms in o(n) Space

pdf-format:
LIPIcs-ICALP-2016-18.pdf (0.6 MB)

Abstract

In this paper we study graph problems in dynamic streaming model, where the input is defined by a sequence of edge insertions and deletions. As many natural problems require Omega(n) space, where n is the number of vertices, existing works mainly focused on designing ~O(n) space algorithms. Although sublinear in the number of edges for dense graphs, it could still be too large for many applications (e.g. n is huge or the graph is sparse). In this work, we give single-pass algorithms beating this space barrier for two classes of problems. We present o(n) space algorithms for estimating the number of connected components with additive error epsilon*n and (1 + epsilon)-approximating the weight of minimum spanning tree. The latter improves previous ~O(n) space algorithm given by Ahn et al. (SODA 2012) for connected graphs with bounded edge weights. We initiate the study of approximate graph property testing in the dynamic streaming model, where we want to distinguish graphs satisfying the property from graphs that are epsilon-far from having the property. We consider the problem of testing k-edge connectivity, k-vertex connectivity, cycle-freeness and bipartiteness (of planar graphs), for which, we provide algorithms using roughly ~O(n^{1-epsilon}) space, which is o(n) for any constant epsilon. To complement our algorithms, we present Omega(n^{1-O(epsilon)}) space lower bounds for these problems, which show that such a dependence on epsilon is necessary.

BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs:2016:6280,
  author =	{Zengfeng Huang and Pan Peng},
  title =	{{Dynamic Graph Stream Algorithms in o(n) Space}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6280},
  URN =		{urn:nbn:de:0030-drops-62801},
  doi =		{10.4230/LIPIcs.ICALP.2016.18},
  annote =	{Keywords: dynamic graph streams, sketching, property testing, minimum spanning tree}
}

Keywords: dynamic graph streams, sketching, property testing, minimum spanning tree
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI