Cormode, Graham ;
Dark, Jacques ;
Konrad, Christian
Independent Sets in VertexArrival Streams
Abstract
We consider the maximal and maximum independent set problems in three models of graph streams:
 In the edge model we see a stream of edges which collectively define a graph; this model is wellstudied for a variety of problems. We show that the space complexity for a onepass streaming algorithm to find a maximal independent set is quadratic (i.e. we must store all edges). We further show that it is not much easier if we only require approximate maximality. This contrasts strongly with the other two vertexbased models, where one can greedily find an exact solution in only the space needed to store the independent set.
 In the "explicit" vertex model, the input stream is a sequence of vertices making up the graph. Every vertex arrives along with its incident edges that connect to previously arrived vertices. Various graph problems require substantially less space to solve in this setting than in edgearrival streams. We show that every onepass capproximation streaming algorithm for maximum independent set (MIS) on explicit vertex streams requires Omega({n^2}/{c^6}) bits of space, where n is the number of vertices of the input graph. It is already known that Theta~({n^2}/{c^2}) bits of space are necessary and sufficient in the edge arrival model (Halldórsson et al. 2012), thus the MIS problem is not significantly easier to solve under the explicit vertex arrival order assumption. Our result is proved via a reduction from a new multiparty communication problem closely related to pointer jumping.
 In the "implicit" vertex model, the input stream consists of a sequence of objects, one per vertex. The algorithm is equipped with a function that maps pairs of objects to the presence or absence of edges, thus defining the graph. This model captures, for example, geometric intersection graphs such as unit disc graphs. Our final set of results consists of several improved upper and lower bounds for interval and square intersection graphs, in both explicit and implicit streams. In particular, we show a gap between the hardness of the explicit and implicit vertex models for interval graphs.
BibTeX  Entry
@InProceedings{cormode_et_al:LIPIcs:2019:10621,
author = {Graham Cormode and Jacques Dark and Christian Konrad},
title = {{Independent Sets in VertexArrival Streams}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {45:145:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10621},
URN = {urn:nbn:de:0030drops106212},
doi = {10.4230/LIPIcs.ICALP.2019.45},
annote = {Keywords: streaming algorithms, independent set size, lower bounds}
}
04.07.2019
Keywords: 

streaming algorithms, independent set size, lower bounds 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 