Distributed Weighted Vertex Cover via Maximal Matchings

In this paper 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 ${\mathrm{O}}(\log n + \log \hat{W})$ communication rounds, where $\hat{W}$ is the average vertex-weight. The previous best algorithm for this problem requires ${\mathrm{O}}(\log n(\log n + \log \hat{W}))$ 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.