Sequential Monte Carlo for counting vertex covers in general graphs

A.A.N. Ridder, Z. Botev, R. Vaisman

Research output: Contribution to JournalArticleAcademicpeer-review


In this paper we describe a sequential importance sampling (SIS) procedure for counting the number of vertex covers in general graphs. The optimal SIS proposal distribution is the uniform over a suitably restricted set, but is not implementable. We will consider two proposal distributions as approximations to the optimal. Both proposals are based on randomization techniques. The first randomization is the classic probability model of random graphs, and in fact, the resulting SIS algorithm shows polynomial complexity for random graphs. The second randomization introduces a probabilistic relaxation technique that uses Dynamic Programming. The numerical experiments show that the resulting SIS algorithm enjoys excellent practical performance in comparison with 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.
Original languageEnglish
Pages (from-to)591-607
Number of pages18
JournalStatistics and Computing
Issue number3
Publication statusPublished - 2016


Dive into the research topics of 'Sequential Monte Carlo for counting vertex covers in general graphs'. Together they form a unique fingerprint.

Cite this