Sequential Monte Carlo for counting vertex covers in general graphs

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

Research output: Contribution to JournalArticleAcademicpeer-review

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.
Original languageEnglish
Pages (from-to)591-607
Number of pages18
JournalStatistics and Computing
Volume26
Issue number3
DOIs
Publication statusPublished - 2016

Fingerprint

Sequential Importance Sampling
Sequential Monte Carlo
Importance sampling
Vertex Cover
Counting
Randomisation
Graph in graph theory
Random Graphs
Belief Networks
Polynomial Complexity
Algorithm Complexity
Sampling Distribution
Importance Sampling
Probability Model
Dynamic Programming
Bayesian networks
Dynamic programming
Numerical Experiment
Graph
Polynomials

Cite this

Ridder, A.A.N. ; Botev, Z. ; Vaisman, R. / Sequential Monte Carlo for counting vertex covers in general graphs. In: Statistics and Computing. 2016 ; Vol. 26, No. 3. pp. 591-607.
@article{e8f029b5b3fa4ea587d35ac0c5c34b73,
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 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.",
author = "A.A.N. Ridder and Z. Botev and R. Vaisman",
year = "2016",
doi = "10.1007/s11222-015-9546-9",
language = "English",
volume = "26",
pages = "591--607",
journal = "Statistics and Computing",
issn = "0960-3174",
publisher = "Springer Netherlands",
number = "3",

}

Sequential Monte Carlo for counting vertex covers in general graphs. / Ridder, A.A.N.; Botev, Z.; Vaisman, R.

In: Statistics and Computing, Vol. 26, No. 3, 2016, p. 591-607.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Sequential Monte Carlo for counting vertex covers in general graphs

AU - Ridder, A.A.N.

AU - Botev, Z.

AU - Vaisman, R.

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

U2 - 10.1007/s11222-015-9546-9

DO - 10.1007/s11222-015-9546-9

M3 - Article

VL - 26

SP - 591

EP - 607

JO - Statistics and Computing

JF - Statistics and Computing

SN - 0960-3174

IS - 3

ER -