P. Crescenzi and L. Trevisan,
On the Distributed Decision-Making Complexity of the Minimum Vertex Cover Problem.
To appear on RAIRO Inf. Theor. Appl., 1996.
Preliminary version in Proc. 20th Workshop on Graph-Theoretic Concepts in Computer Science, LNCS 903, 1995, pages 130-139.
The Min Vertex Cover problem is studied under the distributed decision-making model proposed by Papadimitriou and Yannakakis in 1991. We prove that in a system formed by p processors, under a reasonable information regime, the problem cannot be approximated within a constant ratio smaller than p, and we provide an algorithm that achieves this optimal approximation ratio.