P. Crescenzi and L. Trevisan,
On the Distributed DecisionMaking Complexity of the Minimum
Vertex Cover Problem.
To appear on RAIRO Inf. Theor. Appl., 1996.
Preliminary version in
Proc. 20th Workshop on GraphTheoretic Concepts in Computer
Science, LNCS 903, 1995, pages 130139.
 Abstract

The Min Vertex Cover problem is studied under the
distributed decisionmaking 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.