Computing large independent sets in a single round

Magnús M. Halldórsson, Christian Konrad

Research output: Contribution to journalArticle (Academic Journal)peer-review

197 Downloads (Pure)

Abstract

Independent sets play a central role in distributed algorithmics. We examine here the minimal requirements for computing non-trivial independent sets. In particular, we focus on algorithms that operate in a single communication round. A classic result of Linial shows that a constant number of rounds does not suffice to compute a maximal independent set. We are therefore interested in the size of the solution that can be computed, especially in comparison to the optimal. Our main result is a randomized one-round algorithm that achieves poly-logarithmic approximation on graphs of polynomially bounded-independence. Specifically, we show that the algorithm achieves the Caro-Wei bound (an extension of the Turán bound for independent sets) in general graphs up to a constant factor, and that the Caro-Wei bound yields a poly-logarithmic approximation on bounded-independence graphs. The algorithm uses only a single bit message and operates in a beeping model, where a node receives only the disjunction of the bits transmitted by its neighbors. We give limitation results that show that these are the minimal requirements for obtaining non-trivial solutions. In particular, a sublinear approximation cannot be obtained in a single round on general graphs, nor when nodes cannot both transmit and receive messages. We also show that our analysis of the Caro-Wei bound on polynomially bounded-independence graphs is tight, and that the poly-logarithmic approximation factor does not extend to O(1)-claw free graphs.
Original languageEnglish
Pages (from-to)69-82
Number of pages14
JournalDistributed Computing
Volume31
Issue number1
Early online date24 Mar 2017
DOIs
Publication statusPublished - Feb 2018

Keywords

  • Maximum independent set
  • Bounded-independence graphs
  • Distributed algorithms
  • Randomized algorithms

Fingerprint

Dive into the research topics of 'Computing large independent sets in a single round'. Together they form a unique fingerprint.

Cite this