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). See attachment for full abstract.