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.APPROX-RANDOM.2015.435
URN: urn:nbn:de:0030-drops-53160
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5316/
Sun, Xiaoming ;
Woodruff, David P.
Tight Bounds for Graph Problems in Insertion Streams
Abstract
Despite the large amount of work on solving graph problems in the data stream model, there do not exist tight space bounds for almost any of them, even in a stream with only edge insertions. For example, for testing connectivity, the upper bound is O(n * log(n)) bits, while the lower bound is only Omega(n) bits. We remedy this situation by providing the first tight Omega(n * log(n)) space lower bounds for randomized algorithms which succeed with constant probability in a stream of edge insertions for a number of graph problems. Our lower bounds apply to testing bipartiteness, connectivity, cycle-freeness, whether a graph is Eulerian, planarity, H-minor freeness, finding a minimum spanning tree of a connected graph, and testing if the diameter of a sparse graph is constant. We also give the first Omega(n * k * log(n)) space lower bounds for deterministic algorithms for k-edge connectivity and k-vertex connectivity; these are optimal in light of known deterministic upper bounds (for k-vertex connectivity we also need to allow edge duplications, which known upper bounds allow). Finally, we give an Omega(n * log^2(n)) lower bound for randomized algorithms approximating the minimum cut up to a constant factor with constant probability in a graph with integer weights between 1 and n, presented as a stream of insertions and deletions to its edges. This lower bound also holds for cut sparsifiers, and gives the first separation of maintaining a sparsifier in the data stream model versus the offline model.
BibTeX - Entry
@InProceedings{sun_et_al:LIPIcs:2015:5316,
author = {Xiaoming Sun and David P. Woodruff},
title = {{Tight Bounds for Graph Problems in Insertion Streams}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {435--448},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-89-7},
ISSN = {1868-8969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5316},
URN = {urn:nbn:de:0030-drops-53160},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.435},
annote = {Keywords: communication complexity, data streams, graphs, space complexity}
}
|
Keywords: |
|
communication complexity, data streams, graphs, space complexity |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
13.08.2015 |
