What cannot be computed locally!

Abstract

We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be approximated by factors Ω(nc/k2/k) and Ω(Δ>1/k/k) for some constant c, where n and Δ denote the number of nodes and the largest degree in the graph. The number of rounds required in order to achieve a constant or even only a polylogarithmic approximation ratio is at least Ω(√log n/log log n) and Ω(logΔ/ log log Δ). By a simple reduction, the latter lower bounds also hold for the construction of maximal matchings and maximal independent sets.