Improved Distributed Approximations for Maximum Independent Set

We present improved results for approximating maximum-weight 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. Bar-Yehuda 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 black-box. 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 speed-up 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 local-ratio 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 1-1/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)