Distributed weighted vertex cover via maximal matchings
Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi · ACM Transactions on Algorithms · 2008
In this article, we consider the problem of computing a minimum-weight vertex-cover in an n -node, weighted, undirected graph G = ( V , E ). We present a fully distributed algorithm for computing vertex covers of weight at most twice the optimum, in the case of integer weights. Our algorithm runs in an expected number of O (log n + log Ŵ ) communication rounds, where Ŵ is the average vertex-weight. The previous best algorithm for this problem requires O (log n (log n + log Ŵ )) rounds and it is not fully distributed. For a maximal matching M in G , it is a well-known fact that any vertex-cover in G needs to have at least | M | vertices. Our algorithm is based on a generalization of this combinatorial lower-bound to the weighted setting.