Behnezhad, Soheil ;
Derakhshan, Mahsa ;
Hajiaghayi, MohammadTaghi ;
Knittel, Marina ;
Saleh, Hamed
Brief Announcement: Streaming and Massively Parallel Algorithms for Edge Coloring
Abstract
A valid edgecoloring of a graph is an assignment of "colors" to its edges such that no two incident edges receive the same color. The goal is to find a proper coloring that uses few colors. In this paper, we revisit this problem in two models of computation specific to massive graphs, the Massively Parallel Computations (MPC) model and the Graph Streaming model:
Massively Parallel Computation. We give a randomized MPC algorithm that w.h.p., returns a (1+o(1))Delta edge coloring in O(1) rounds using O~(n) space per machine and O(m) total space. The space per machine can also be further improved to n^{1Omega(1)} if Delta = n^{Omega(1)}. This is, to our knowledge, the first constant round algorithm for a natural graph problem in the strongly sublinear regime of MPC. Our algorithm improves a previous result of Harvey et al. [SPAA 2018] which required n^{1+Omega(1)} space to achieve the same result.
Graph Streaming. Since the output of edgecoloring is as large as its input, we consider a standard variant of the streaming model where the output is also reported in a streaming fashion. The main challenge is that the algorithm cannot "remember" all the reported edge colors, yet has to output a proper edge coloring using few colors.
We give a onepass O~(n)space streaming algorithm that always returns a valid coloring and uses 5.44 Delta colors w.h.p., if the edges arrive in a random order. For adversarial order streams, we give another onepass O~(n)space algorithm that requires O(Delta^2) colors.
BibTeX  Entry
@InProceedings{behnezhad_et_al:LIPIcs:2019:11343,
author = {Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi and Marina Knittel and Hamed Saleh},
title = {{Brief Announcement: Streaming and Massively Parallel Algorithms for Edge Coloring}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {36:136:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771269},
ISSN = {18688969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11343},
URN = {urn:nbn:de:0030drops113438},
doi = {10.4230/LIPIcs.DISC.2019.36},
annote = {Keywords: Massively Parallel Computation, Streaming, Edge Coloring}
}
08.10.2019
Keywords: 

Massively Parallel Computation, Streaming, Edge Coloring 
Seminar: 

33rd International Symposium on Distributed Computing (DISC 2019)

Issue date: 

2019 
Date of publication: 

08.10.2019 