IDEAS home Printed from https://ideas.repec.org/p/tin/wpaper/20130122.html
   My bibliography  Save this paper

Sequential Monte Carlo for Counting Vertex Covers in General Graphs

Author

Listed:
  • Radislav Vaisman

    (Technion, Haifa, Israel)

  • Zdravko Botev

    (University of New South Wales, Sidney, Australia)

  • Ad Ridder

    (VU University Amsterdam)

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.

Suggested Citation

  • Radislav Vaisman & Zdravko Botev & Ad Ridder, 2013. "Sequential Monte Carlo for Counting Vertex Covers in General Graphs," Tinbergen Institute Discussion Papers 13-122/III, Tinbergen Institute.
    • Handle: RePEc:tin:wpaper:20130122
    as

    Download full text from publisher

    File URL: https://papers.tinbergen.nl/13122.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Yuguo Chen & Persi Diaconis & Susan P. Holmes & Jun S. Liu, 2005. "Sequential Monte Carlo Methods for Statistical Analysis of Tables," Journal of the American Statistical Association, American Statistical Association, vol. 100, pages 109-120, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dyer, Martin & Greenhill, Catherine & Kleer, Pieter & Ross, James & Stougie, Leen, 2021. "Sampling hypergraphs with given degrees," Other publications TiSEM 2d323767-8066-4c28-92cc-b, Tilburg University, School of Economics and Management.
    2. Zhang, Linjun & Small, Michael & Judd, Kevin, 2015. "Exactly scale-free scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 433(C), pages 182-197.
    3. Ian Dinwoodie & Kruti Pandya, 2015. "Exact tests for singular network data," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 67(4), pages 687-706, August.
    4. Jing Xi & Ruriko Yoshida & David Haws, 2013. "Estimating the number of zero-one multi-way tables via sequential importance sampling," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 65(4), pages 763-783, August.
    5. Clemens Draxler, 2018. "Bayesian conditional inference for Rasch models," AStA Advances in Statistical Analysis, Springer;German Statistical Society, vol. 102(2), pages 245-262, April.
    6. Stephen DeSalvo & James Zhao, 2020. "Random sampling of contingency tables via probabilistic divide-and-conquer," Computational Statistics, Springer, vol. 35(2), pages 837-869, June.
    7. Ogawa, Mitsunori & Takemura, Akimichi, 2012. "Markov bases for typical block effect models of two-way contingency tables," Journal of Multivariate Analysis, Elsevier, vol. 112(C), pages 219-229.
    8. Sanda Micula, 2015. "Statistical Computer Simulations And Monte Carlo Methods," Romanian Economic Business Review, Romanian-American University, vol. 9(2), pages 384-394, December.
    9. Bartolucci, Francesco & Pigini, Claudia & Valentini, Francesco, 2021. "MCMC Conditional Maximum Likelihood for the two-way fixed-effects logit," MPRA Paper 110034, University Library of Munich, Germany.
    10. George Fishman, 2014. "Counting subsets of contingency tables," Computational Statistics, Springer, vol. 29(1), pages 159-187, February.
    11. Yuguo Chen & Dylan Small, 2005. "Exact tests for the rasch model via sequential importance sampling," Psychometrika, Springer;The Psychometric Society, vol. 70(1), pages 11-30, March.
    12. David Kahle & Ruriko Yoshida & Luis Garcia-Puente, 2018. "Hybrid schemes for exact conditional inference in discrete exponential families," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 70(5), pages 983-1011, October.
    13. Radislav Vaisman & Dirk P. Kroese, 2017. "Stochastic Enumeration Method for Counting Trees," Methodology and Computing in Applied Probability, Springer, vol. 19(1), pages 31-73, March.
    14. Rivest, Louis-Paul, 2021. "Limiting properties of an equiprobable sampling scheme for 0–1 matrices," Statistics & Probability Letters, Elsevier, vol. 172(C).
    15. repec:jss:jstsof:20:i04 is not listed on IDEAS
    16. Verhelst, Norman & Hatzinger, Reinhold & Mair, Patrick, 2007. "The Rasch Sampler," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 20(i04).
    17. repec:jss:jstsof:17:i07 is not listed on IDEAS
    18. Norman Verhelst, 2008. "An Efficient MCMC Algorithm to Sample Binary Matrices with Fixed Marginals," Psychometrika, Springer;The Psychometric Society, vol. 73(4), pages 705-728, December.
    19. Radislav Vaisman & Ofer Strichman & Ilya Gertsbakh, 2015. "Model Counting of Monotone Conjunctive Normal Form Formulas with Spectra," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 406-415, May.
    20. Drew Creal, 2012. "A Survey of Sequential Monte Carlo Methods for Economics and Finance," Econometric Reviews, Taylor & Francis Journals, vol. 31(3), pages 245-296.
    21. Caffo, Brian, 2006. "Exact Hypothesis Tests for Log-linear Models with exactLoglinTest," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 17(i07).

    More about this item

    Keywords

    Vertex Cover; Counting problem; Sequential importance sampling; Dynamic Programming; Relaxation; Random Graphs;
    All these keywords.

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis
    • C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:tin:wpaper:20130122. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Tinbergen Office +31 (0)10-4088900 (email available below). General contact details of provider: https://edirc.repec.org/data/tinbenl.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.