Abstract
We present improved results for approximating maximumweight independent set (MaxIS) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let n and Δ be the number of nodes and maximum degree, respectively, and let MIS(n,Δ) be the running time of finding a maximal independent set (MIS) in the CONGEST model. BarYehuda et al. [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a Δapproximation for MaxIS in O(MIS(n,Δ)log W) rounds, where W is the maximum weight of a node in the graph, which can be as large as poly (n). Whether their algorithm is deterministic or randomized that succeeds with high probability depends on the MIS algorithm that is used as a blackbox. Our results:
1) A deterministic O(MIS(n,Δ)/ε)round algorithm that finds a (1+ε)Δapproximation for MaxIS in the CONGEST model.
2) A randomized (poly(log log n)/ε)round algorithm that finds, with high probability, a (1+ε)Δapproximation for MaxIS in the CONGEST model. That is, by sacrificing only a tiny fraction of the approximation guarantee, we achieve an exponential speedup in the running time over the previous best known result.
3) A randomized O(log n⋅ poly(log log n)/ε)round algorithm that finds, with high probability, a 8(1+ε)αapproximation for MaxIS in the CONGEST model, where α is the arboricity of the graph. For graphs of arboricity α < Δ/(8(1+ε)), this result improves upon the previous best known result in both the approximation factor and the running time.
One may wonder whether it is possible to approximate MaxIS with high probability in fewer than poly(log log n) rounds. Interestingly, a folklore randomized ranking algorithm by Boppana implies a single round algorithm that gives an expected Δapproximation in the CONGEST model. However, it is unclear how to convert this algorithm to one that succeeds with high probability without sacrificing a large number of rounds. For unweighted graphs of maximum degree Δ ≤ n/log n, we show a new analysis of the randomized ranking algorithm, which we combine with the localratio technique, to provide a O(1/ε)round algorithm in the CONGEST model that, with high probability, finds an independent set of size at least n/((1+ε)(Δ+1)). This result cannot be extended to very high degree graphs, as we show a lower bound of Ω(log^*n) rounds for any randomized algorithm that with probability at least 11/log n finds an independent set of size Ω(n/Δ). This lower bound holds even for the LOCAL model. The hard instances that we use to prove our lower bound are graphs of maximum degree Δ = Ω(n/log^*n).
BibTeX  Entry
@InProceedings{kawarabayashi_et_al:LIPIcs:2020:13113,
author = {Kenichi Kawarabayashi and Seri Khoury and Aaron Schild and Gregory Schwartzman},
title = {{Improved Distributed Approximations for Maximum Independent Set}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {35:135:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771689},
ISSN = {18688969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13113},
URN = {urn:nbn:de:0030drops131135},
doi = {10.4230/LIPIcs.DISC.2020.35},
annote = {Keywords: Distributed graph algorithms, Approximation algorithms, Lower bounds}
}
Keywords: 

Distributed graph algorithms, Approximation algorithms, Lower bounds 
Collection: 

34th International Symposium on Distributed Computing (DISC 2020) 
Issue Date: 

2020 
Date of publication: 

07.10.2020 