We present a simple deterministic distributed (2+ ) approximation algorithm for minimum weight vertex cover, which completes in O(log ∆/ log log ∆) rounds, where ∆ is the maximum degree in the graph, for any > 0 which is at most O(1). For a constant , this implies a constant approximation in O(log ∆/ log log ∆) rounds, which contradicts the lower bound of [KMW10] .
As for approximations, an optimal (for constant values of ) (2 + )-approximate deterministic algorithm (for the weighted variant) in the CONGEST running in O( −1 log ∆/ log log ∆) rounds is given in REF .
A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
PODC '16
Mathematics Computer Science