Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs

We design new deterministic CONGEST approximation algorithms for \emph{maximum weight independent set (MWIS)} in \emph{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^{2} (ΔW)\cdot \log (1/ε)+\log ^{*}n)$-round algorithm, where $W$ is the largest node-weight (this bound translates to $O(\log^{2} n\cdot\log (1/ε))$ under the common assumption that $W=\text{poly}(n)$). As for $α$-dependent approximations, a deterministic CONGEST $(8(1+ε)\cdotα)$-approximation algorithm with runtime $O(\log^{3} n\cdot\log (1/ε))$ can be derived by combining the aforementioned algorithm of Faour et al.\ with a method presented by Kawarabayashi et al.\ [DISC 2020].