Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs

We design new deterministic CONGEST approximation algorithms for maximum weight independent set (MWIS) in sparse graphs. As our main results, we obtain new Δ(1+ε)-approximation algorithms as well as algorithms whose approximation ratio depend strictly on α, in graphs with maximum degree Δ and arboricity α. For (deterministic) Δ(1+ε)-approximation, the current state-of-the-art is due to a recent breakthrough by Faour et al.\ [SODA 2023] that showed an O(log² (Δ W)· log (1/ε)+log *n)-round algorithm, where W is the largest node-weight (this bound translates to O(log² n·log (1/ε)) under the common assumption that W=poly(n)). As for α-dependent approximations, a deterministic CONGEST (8(1+ε)·α)-approximation algorithm with runtime O(log³ n·log (1/ε)) can be derived by combining the aforementioned algorithm of Faour et al.\ with a method presented by Kawarabayashi et al.\ [DISC 2020].