Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets

Shreyas Pai; Gopal Pandurangan; Sriram V Pemmaraju; Talal Riaz; Peter Robinson

doi:10.48550/arxiv.1705.07861

Back

Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets

Preprint

Open access

Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets

Shreyas Pai, Gopal Pandurangan, Sriram V Pemmaraju, Talal Riaz and Peter Robinson

ArXiv.org

05/22/2017

DOI: 10.48550/arxiv.1705.07861

Files and links (1)

url

https://doi.org/10.48550/arxiv.1705.07861View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

We study local symmetry breaking problems in the CONGEST model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. A $\beta$-ruling set is an independent set such that every node in the graph is at most $\beta$ hops from a node in the independent set. Our work is motivated by the following central question: can we break the $\Theta(\log n)$ time complexity barrier and the $\Theta(m)$ message complexity barrier in the CONGEST model for MIS or closely-related symmetry breaking problems? We present the following results: - Time Complexity: We show that we can break the $O(\log n)$ "barrier" for 2- and 3-ruling sets. We compute 3-ruling sets in $O\left(\frac{\log n}{\log \log n}\right)$ rounds with high probability (whp). More generally we show that 2-ruling sets can be computed in $O\left(\log \Delta \cdot (\log n)^{1/2 + \varepsilon} + \frac{\log n}{\log\log n}\right)$ rounds for any $\varepsilon > 0$, which is $o(\log n)$ for a wide range of $\Delta$ values (e.g., $\Delta = 2^{(\log n)^{1/2-\varepsilon}}$). These are the first 2- and 3-ruling set algorithms to improve over the $O(\log n)$-round complexity of Luby's algorithm in the CONGEST model. - Message Complexity: We show an $\Omega(n^2)$ lower bound on the message complexity of computing an MIS (i.e., 1-ruling set) which holds also for randomized algorithms and present a contrast to this by showing a randomized algorithm for 2-ruling sets that, whp, uses only $O(n \log^2 n)$ messages and runs in $O(\Delta \log n)$ rounds. This is the first message-efficient algorithm known for ruling sets, which has message complexity nearly linear in $n$ (which is optimal up to a polylogarithmic factor).

Details

Title: Subtitle: Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets
Creators: Shreyas Pai
Gopal Pandurangan
Sriram V Pemmaraju
Talal Riaz
Peter Robinson
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.1705.07861
ISSN: 2331-8422
Language: English
Date posted: 05/22/2017
Academic Unit: Computer Science
Record Identifier: 9984411068202771

Metrics

1 Record Views