Sequential Monte Carlo for Counting Vertex Covers in General Graphs

Radislav Vaisman, Zdravko Botev and Ad Ridder
Additional contact information
Radislav Vaisman: Technion, Haifa, Israel
Zdravko Botev: University of New South Wales, Sidney, Australia
Ad Ridder: VU University Amsterdam

No 13-122/III, Tinbergen Institute Discussion Papers from Tinbergen Institute

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.

Keywords: Vertex Cover; Counting problem; Sequential importance sampling; Dynamic Programming; Relaxation; Random Graphs (search for similar items in EconPapers)
JEL-codes: C61 C63 (search for similar items in EconPapers)
Date: 2013-08-26
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://papers.tinbergen.nl/13122.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:tin:wpaper:20130122

Access Statistics for this paper

More papers in Tinbergen Institute Discussion Papers from Tinbergen Institute Contact information at EDIRC.
Bibliographic data for series maintained by Tinbergen Office +31 (0)10-4088900 ().