Abstract
The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related betaruling set problem, in two computational models suited for largescale graph processing, namely the kmachine model and the graph streaming model. We present a number of results. For MIS in the kmachine model, we improve the O~(m/k^2 + Delta/k)round upper bound of Klauck et al. (SODA 2015) by presenting an O~(m/k^2)round algorithm. We also present an Omega~(n/k^2) round lower bound for MIS, the first lower bound for a symmetry breaking problem in the kmachine model. For betaruling sets, we use hierarchical sampling to obtain more efficient algorithms in the kmachine model and also in the graph streaming model. More specifically, we obtain a kmachine algorithm that runs in O~(beta n Delta^{1/beta}/k^2) rounds and, by using a similar hierarchical sampling technique, we obtain onepass algorithms for both insertiononly and insertiondeletion streams that use O(beta * n^{1+1/2^{beta1}}) space. The latter result establishes a clear separation between MIS, which is known to require Omega(n^2) space (Cormode et al., ICALP 2019), and betaruling sets, even for beta = 2. Finally, we present an even faster 2ruling set algorithm in the kmachine model, one that runs in O~(n/k^{2epsilon} + k^{1epsilon}) rounds for any epsilon, 0 <=epsilon <=1. For a wide range of values of k this round complexity simplifies to O~(n/k^2) rounds, which we conjecture is optimal.
Our results use a variety of techniques. For our upper bounds, we prove and use simulation theorems for beeping algorithms, hierarchical sampling, and L_0sampling, whereas for our lower bounds we use informationtheoretic arguments and reductions to 2party communication complexity problems.
BibTeX  Entry
@InProceedings{konrad_et_al:LIPIcs:2019:11333,
author = {Christian Konrad and Sriram V. Pemmaraju and Talal Riaz and Peter Robinson},
title = {{The Complexity of Symmetry Breaking in Massive Graphs}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {26:126:18},
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/11333},
URN = {urn:nbn:de:0030drops113337},
doi = {10.4230/LIPIcs.DISC.2019.26},
annote = {Keywords: communication complexity, information theory, kmachine model, maximal independent set, ruling set, streaming algorithms}
}
Keywords: 

communication complexity, information theory, kmachine model, maximal independent set, ruling set, streaming algorithms 
Collection: 

33rd International Symposium on Distributed Computing (DISC 2019) 
Issue Date: 

2019 
Date of publication: 

08.10.2019 