Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs
<|reference_start|>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 $\Delta(1+\epsilon)$-approximation algorithms as well as algorithms whose approximation ratio depend strictly on $\alpha$, in graphs with maximum degree $\Delta$ and arboricity $\alpha$. For (deterministic) $\Delta(1+\epsilon)$-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} (\Delta W)\cdot \log (1/\epsilon)+\log ^{*}n)$-round algorithm, where $W$ is the largest node-weight (this bound translates to $O(\log^{2} n\cdot\log (1/\epsilon))$ under the common assumption that $W=\text{poly}(n)$). As for $\alpha$-dependent approximations, a deterministic CONGEST $(8(1+\epsilon)\cdot\alpha)$-approximation algorithm with runtime $O(\log^{3} n\cdot\log (1/\epsilon))$ can be derived by combining the aforementioned algorithm of Faour et al.\ with a method presented by Kawarabayashi et al.\ [DISC 2020].<|reference_end|>
@article{gil2024improved,
    title={Improved Deterministic Distributed Maximum Weight Independent Set
  Approximation in Sparse Graphs},
    author={Yuval Gil},
    journal={arXiv preprint arXiv:2402.09011},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.09011},
    primaryClass={cs.DS cs.DC}
}