Distributed Approximation of Maximum Independent Set and Maximum Matching
Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, Gregory Schwartzman · 2017
We present a simple distributed Δ-approximation algorithm for maximum weight independent set (MaxIS) in the CONGEST model which completes in O(MIS ⋅ log W) rounds, where Δ is the maximum degree, MIS is the number of rounds needed to compute a maximal independent set (MIS) on G, and W is the maximum weight of a node. Plugging in the best known algorithm for MIS gives a randomized solution in O(log n log W) rounds, where n is the number of nodes. We also present a deterministic O(Δ +log* n)-round algorithm based on coloring.