### Abstract

Original language | English |
---|---|

Pages (from-to) | 591-607 |

Number of pages | 18 |

Journal | Statistics and Computing |

Volume | 26 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2016 |

### Fingerprint

### Cite this

*Statistics and Computing*,

*26*(3), 591-607. https://doi.org/10.1007/s11222-015-9546-9

}

*Statistics and Computing*, vol. 26, no. 3, pp. 591-607. https://doi.org/10.1007/s11222-015-9546-9

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

Research output: Contribution to Journal › Article › Academic › peer-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 -