What cannot be computed locally! 论文

摘要

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.