What cannot be computed locally!
Fabian Kühn, Thomas Moscibroda, Rogert Wattenhofer · 2004
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.