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.2020.11
URN: urn:nbn:de:0030-drops-124182
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12418/
Bera, Suman K. ;
Chakrabarti, Amit ;
Ghosh, Prantar
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models
Abstract
We study the problem of coloring a given graph using a small number of colors in several well-established models of computation for big data. These include the data streaming model, the general graph query model, the massively parallel communication (MPC) model, and the CONGESTED-CLIQUE and the LOCAL models of distributed computation. On the one hand, we give algorithms with sublinear complexity, for the appropriate notion of complexity in each of these models. Our algorithms color a graph G using κ(G)⋅(1+o(1)) colors, where κ(G) is the degeneracy of G: this parameter is closely related to the arboricity α(G). As a function of κ(G) alone, our results are close to best possible, since the optimal number of colors is κ(G)+1. For several classes of graphs, including real-world "big graphs," our results improve upon the number of colors used by the various (Δ(G)+1)-coloring algorithms known for these models, where Δ(G) is the maximum degree in G, since Δ(G) ⩾ κ(G) and can in fact be arbitrarily larger than κ(G).
On the other hand, we establish certain lower bounds indicating that sublinear algorithms probably cannot go much further. In particular, we prove that any randomized coloring algorithm that uses at most κ(G)+O(1) colors would require Ω(n²) storage in the one pass streaming model, and Ω(n²) many queries in the general graph query model, where n is the number of vertices in the graph. These lower bounds hold even when the value of κ(G) is known in advance; at the same time, our upper bounds do not require κ(G) to be given in advance.
BibTeX - Entry
@InProceedings{bera_et_al:LIPIcs:2020:12418,
author = {Suman K. Bera and Amit Chakrabarti and Prantar Ghosh},
title = {{Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {11:1--11:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12418},
URN = {urn:nbn:de:0030-drops-124182},
doi = {10.4230/LIPIcs.ICALP.2020.11},
annote = {Keywords: Data streaming, Graph coloring, Sublinear algorithms, Massively parallel communication, Distributed algorithms}
}
|
Keywords: |
|
Data streaming, Graph coloring, Sublinear algorithms, Massively parallel communication, Distributed algorithms |
|
Collection: |
|
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
29.06.2020 |
