The complexity of symmetry breaking in massive graphs
- Christian Konrad,
- Sriram V. Pemmaraju,
- Talal Riaz,
- University of Bristol,
- University of Iowa,
- City University of Hong Kong
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Research
Related Event
Title
33rd International Symposium on Distributed Computing, DISC 2019
Event type
ConferenceDate
10/14/2019 - 10/18/2019Location
BudapestHungary
Abstract
<p>The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related β-ruling set problem, in two computational models suited for large-scale graph processing, namely the k-machine model and the graph streaming model. We present a number of results. For MIS in the k-machine model, we improve the Õ(m/k<sup>2</sup> + ∆/k)-round upper bound of Klauck et al. (SODA 2015) by presenting an Õ(m/k<sup>2</sup>)-round algorithm. We also present an Ω(n/k<sup>2</sup>) round lower bound for MIS, the first lower bound for a symmetry breaking problem in the k-machine model. For β-ruling sets, we use hierarchical sampling to obtain more efficient algorithms in the k-machine model and also in the graph streaming model. More specifically, we obtain a k-machine algorithm that runs in Õ(βn∆<sup>1/β</sup>/k<sup>2</sup>) rounds and, by using a similar hierarchical sampling technique, we obtain one-pass algorithms for both insertion-only and insertion-deletion streams that use O(β · n<sup>1+1</sup>/<sup>2β</sup>−<sup>1</sup>) space. The latter result establishes a clear separation between MIS, which is known to require Ω(n<sup>2</sup>) space (Cormode et al., ICALP 2019), and β-ruling sets, even for β = 2. Finally, we present an even faster 2-ruling set algorithm in the k-machine model, one that runs in Õ(n/k<sup>2</sup>−ε + k<sup>1</sup>−ε) rounds for any ε, 0 ≤ ε ≤ 1. For a wide range of values of k this round complexity simplifies to Õ(n/k<sup>2</sup>) 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 L0-sampling, whereas for our lower bounds we use information-theoretic arguments and reductions to 2-party communication complexity problems.</p>
Publication Information
Output type
Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Research
Original language
English (US)Article number
26Publication milestones
- Published - 10/2019
Publication status
Published - 10/2019
Publisher
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, GermanyPublication series
- Publication series name: Leibniz International Proceedings in Informatics, LIPIcs
ISSN (Print): 1868-8969
Volume: 146
ISBN (Electronic)
9783959771269Publication IDs
- Scopus: 85074555019
Host publication title
33rd International Symposium on Distributed Computing, DISC 2019Host publication editors
- Jukka Suomela
Publication metrics
Metrics
Fractional count
1
Fractional count
0.25
Fractional count
3
Fractional count
0.75
Fractional count
1
Fractional count
1
PlumX, opens in new tab
Citation count
10
