A Deterministic Distributed $2$-Approximation for Weighted Vertex Cover in $O(\log n\log \Delta /{\log }^2\log \Delta )$ Rounds

Abstract

We present a deterministic distributed $2$-approximation algorithm for the Minimum Weight Vertex Cover problem in the CONGEST model whose round complexity is $O(\log n\log \Delta /{\log }^2\log \Delta )$. This improves over the currently best known deterministic 2-approximation implied by [KVY94]. Our solution generalizes the $(2+\epsilon )$-approximation algorithm of [BCS17], improving the dependency on ${\epsilon }^{-1}$ from linear to logarithmic. In addition, for every $\epsilon =(\log \Delta {)}^{-c}$, where $c\ge 1$ is a constant, our algorithm computes a $(2+\epsilon )$-approximation in $O(\log \Delta /\log \log \Delta )$~rounds (which is asymptotically optimal).

To appear in SIROCCO 2018