Template-Type: ReDIF-Paper 1.0
Series: Tinbergen Institute Discussion Papers
Creation-Date: 2013-08-26
Number: 13-122/III
Author-Name: Radislav Vaisman
Author-Workplace-Name: Technion, Haifa, Israel
Author-Name: Zdravko Botev
Author-Workplace-Name: University of New South Wales, Sidney, Australia
Author-Name: Ad Ridder
Author-Workplace-Name: VU University Amsterdam
Title: Sequential Monte Carlo for Counting Vertex Covers in General Graphs
Abstract: 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.
Classification-JEL: C61, C63
Keywords: Vertex Cover, Counting problem, Sequential importance sampling, Dynamic Programming, Relaxation, Random Graphs
File-Url: https://papers.tinbergen.nl/13122.pdf
File-Format: application/pdf
File-Size: 204990 bytes
Handle: RePEc:tin:wpaper:20130122