The Library
Independent sets in vertex-arrival streams
Tools
Tools
Tools
Cormode, Graham, Dark, Jacques and Konrad, Christian (2019) Independent sets in vertex-arrival streams. In: 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 8-12 Jul 2019. Published in: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) 45-1-45-14. ISBN 9783959771092. doi:10.4230/LIPIcs.ICALP.2019.45 ISSN 1868-8969.
|
PDF
WRAP-independent-sets-vertex-arrival-streams-Cormode-2019.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (561Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.45
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 well-studied for a variety of problems. We show that the space complexity for a one-pass 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 vertex-based 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 edge-arrival streams. We show that every one-pass c-approximation 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 multi-party 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.
| Item Type: | Conference Item (Paper) | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory | ||||||||||||||||||
| Journal or Publication Title: | 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) | ||||||||||||||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||||||||||||||
| ISBN: | 9783959771092 | ||||||||||||||||||
| ISSN: | 1868-8969 | ||||||||||||||||||
| Official Date: | 2019 | ||||||||||||||||||
| Dates: |
|
||||||||||||||||||
| Page Range: | 45-1-45-14 | ||||||||||||||||||
| DOI: | 10.4230/LIPIcs.ICALP.2019.45 | ||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||
| Publication Status: | Published | ||||||||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||||||||
| Date of first compliant deposit: | 20 May 2019 | ||||||||||||||||||
| Date of first compliant Open Access: | 29 May 2019 | ||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||||||||
| Conference Paper Type: | Paper | ||||||||||||||||||
| Title of Event: | 46th International Colloquium on Automata, Languages and Programming | ||||||||||||||||||
| Type of Event: | Conference | ||||||||||||||||||
| Location of Event: | Patras, Greece | ||||||||||||||||||
| Date(s) of Event: | 8-12 Jul 2019 | ||||||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
