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.ITCS.2021.15
URN: urn:nbn:de:0030-drops-135544
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13554/
Bhattacharya, Anup ;
Bishnu, Arijit ;
Mishra, Gopinath ;
Upasana, Anannya
Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming!
Abstract
We study a graph coloring problem that is otherwise easy in the RAM model but becomes quite non-trivial in the one-pass streaming model. In contrast to previous graph coloring problems in streaming that try to find an assignment of colors to vertices, our main work is on estimating the number of conflicting or monochromatic edges given a coloring function that is streaming along with the graph; we call the problem Conflict-Est. The coloring function on a vertex can be read or accessed only when the vertex is revealed in the stream. If we need the color on a vertex that has streamed past, then that color, along with its vertex, has to be stored explicitly. We provide algorithms for a graph that is streaming in different variants of the vertex arrival in one-pass streaming model, viz. the Vertex Arrival (VA), Vertex Arrival With Degree Oracle (VAdeg), Vertex Arrival in Random Order (VArand) models, with special focus on the random order model. We also provide matching lower bounds for most of the cases. The mainstay of our work is in showing that the properties of a random order stream can be exploited to design efficient streaming algorithms for estimating the number of monochromatic edges. We have also obtained a lower bound, though not matching the upper bound, for the random order model. Among all the three models vis-a-vis this problem, we can show a clear separation of power in favor of the VArand model.
BibTeX - Entry
@InProceedings{bhattacharya_et_al:LIPIcs.ITCS.2021.15,
author = {Anup Bhattacharya and Arijit Bishnu and Gopinath Mishra and Anannya Upasana},
title = {{Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming!}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {15:1--15:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-177-1},
ISSN = {1868-8969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13554},
URN = {urn:nbn:de:0030-drops-135544},
doi = {10.4230/LIPIcs.ITCS.2021.15},
annote = {Keywords: Streaming, random ordering, graph coloring, estimation, lower bounds}
}
|
Keywords: |
|
Streaming, random ordering, graph coloring, estimation, lower bounds |
|
Collection: |
|
12th Innovations in Theoretical Computer Science Conference (ITCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.02.2021 |
