# 13-122/III (2013-08-26)

Radislav Vaisman, Technion, Haifa, Israel; Zdravko Botev, University of New South Wales, Sidney, Australia; Ad Ridder, VU University Amsterdam
Vertex Cover, Counting problem, Sequential importance sampling, Dynamic Programming, Relaxation, Random Graphs
JEL codes:
C61, C63

In this paper we describe a Sequential Importance Sampling (SIS) procedure for counting the number of vertex covers in general graphs. The performance of SIS depends heavily on how close the SIS proposal distribution is to a uniform one over a suitably restricted set. The proposed algorithm introduces a probabilistic relaxation technique that uses Dynamic Programming in order to efficiently estimate this uniform distribution. The numerical experiments show that the scheme compares favorably with other existing methods. In particular the method is compared with cachet - an exact model counter, and the state of the art SampleSearch, which is based on Belief Networks and importance sampling.