  We introduce a simple, efficient and precise polynomial heuristic for a key
NP complete problem, minimum vertex cover. Our method is iterative and operates
in probability space. Once a stable probability solution is found we find the
true combinatorial solution from the probabilities. For system sizes which are
amenable to exact solution by conventional means, we find a correct minimum
vertex cover for all cases which we have tested, which include random graphs
and diluted triangular lattices of up to 100 sites. We present precise data for
minimum vertex cover on graphs of up to 50,000 sites. Extensions of the method
to hard core lattices gases and other NP problems are discussed.

Statistical Mechanics