Brief Announcement: Improved Distributed Approximations for Maximum-Weight Independent Set
Ken‐ichi Kawarabayashi, Seri Khoury, Aaron Schild, Gregory Schwartzman · 2020
We present improved algorithms for approximating maximum-weight independent set (MaxIS) in the CONGEST model. 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 high as poly(n). Whether their algorithm is deterministic or randomized depends on the MIS algorithm that is used as a black-box. Our results: