Sequential Monte Carlo for counting vertex covers in general graphs

Vaisman, Radislav, Botev, Zdravko I. and Ridder, Ad (2016) Sequential Monte Carlo for counting vertex covers in general graphs. Statistics and Computing, 26 3: 591-607. doi:10.1007/s11222-015-9546-9

Author Vaisman, Radislav
Botev, Zdravko I.
Ridder, Ad
Title Sequential Monte Carlo for counting vertex covers in general graphs
Journal name Statistics and Computing   Check publisher's open access policy
ISSN 0960-3174
Publication date 2016-05
Year available 2016
Sub-type Article (original research)
DOI 10.1007/s11222-015-9546-9
Open Access Status Not Open Access
Volume 26
Issue 3
Start page 591
End page 607
Total pages 17
Place of publication New York, NY United States
Publisher Springer New York
Collection year 2017
Language eng
Formatted abstract
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.
Keyword Vertex cover
Counting problem
Sequential importance sampling
Dynamic programming
Random graphs
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
HERDC Pre-Audit
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Sun, 22 May 2016, 00:20:39 EST by System User on behalf of School of Mathematics & Physics