Cargando…
Approximate Counting of Graphical Realizations
In 1999 Kannan, Tetali and Vempala proposed a MCMC method to uniformly sample all possible realizations of a given graphical degree sequence and conjectured its rapidly mixing nature. Recently their conjecture was proved affirmative for regular graphs (by Cooper, Dyer and Greenhill, 2007), for regul...
Autores principales: | , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Public Library of Science
2015
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4498913/ https://www.ncbi.nlm.nih.gov/pubmed/26161994 http://dx.doi.org/10.1371/journal.pone.0131300 |
_version_ | 1782380705846657024 |
---|---|
author | Erdős, Péter L. Kiss, Sándor Z. Miklós, István Soukup, Lajos |
author_facet | Erdős, Péter L. Kiss, Sándor Z. Miklós, István Soukup, Lajos |
author_sort | Erdős, Péter L. |
collection | PubMed |
description | In 1999 Kannan, Tetali and Vempala proposed a MCMC method to uniformly sample all possible realizations of a given graphical degree sequence and conjectured its rapidly mixing nature. Recently their conjecture was proved affirmative for regular graphs (by Cooper, Dyer and Greenhill, 2007), for regular directed graphs (by Greenhill, 2011) and for half-regular bipartite graphs (by Miklós, Erdős and Soukup, 2013). Several heuristics on counting the number of possible realizations exist (via sampling processes), and while they work well in practice, so far no approximation guarantees exist for such an approach. This paper is the first to develop a method for counting realizations with provable approximation guarantee. In fact, we solve a slightly more general problem; besides the graphical degree sequence a small set of forbidden edges is also given. We show that for the general problem (which contains the Greenhill problem and the Miklós, Erdős and Soukup problem as special cases) the derived MCMC process is rapidly mixing. Further, we show that this new problem is self-reducible therefore it provides a fully polynomial randomized approximation scheme (a.k.a. FPRAS) for counting of all realizations. |
format | Online Article Text |
id | pubmed-4498913 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2015 |
publisher | Public Library of Science |
record_format | MEDLINE/PubMed |
spelling | pubmed-44989132015-07-17 Approximate Counting of Graphical Realizations Erdős, Péter L. Kiss, Sándor Z. Miklós, István Soukup, Lajos PLoS One Research Article In 1999 Kannan, Tetali and Vempala proposed a MCMC method to uniformly sample all possible realizations of a given graphical degree sequence and conjectured its rapidly mixing nature. Recently their conjecture was proved affirmative for regular graphs (by Cooper, Dyer and Greenhill, 2007), for regular directed graphs (by Greenhill, 2011) and for half-regular bipartite graphs (by Miklós, Erdős and Soukup, 2013). Several heuristics on counting the number of possible realizations exist (via sampling processes), and while they work well in practice, so far no approximation guarantees exist for such an approach. This paper is the first to develop a method for counting realizations with provable approximation guarantee. In fact, we solve a slightly more general problem; besides the graphical degree sequence a small set of forbidden edges is also given. We show that for the general problem (which contains the Greenhill problem and the Miklós, Erdős and Soukup problem as special cases) the derived MCMC process is rapidly mixing. Further, we show that this new problem is self-reducible therefore it provides a fully polynomial randomized approximation scheme (a.k.a. FPRAS) for counting of all realizations. Public Library of Science 2015-07-10 /pmc/articles/PMC4498913/ /pubmed/26161994 http://dx.doi.org/10.1371/journal.pone.0131300 Text en © 2015 Erdős et al http://creativecommons.org/licenses/by/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are properly credited. |
spellingShingle | Research Article Erdős, Péter L. Kiss, Sándor Z. Miklós, István Soukup, Lajos Approximate Counting of Graphical Realizations |
title | Approximate Counting of Graphical Realizations |
title_full | Approximate Counting of Graphical Realizations |
title_fullStr | Approximate Counting of Graphical Realizations |
title_full_unstemmed | Approximate Counting of Graphical Realizations |
title_short | Approximate Counting of Graphical Realizations |
title_sort | approximate counting of graphical realizations |
topic | Research Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4498913/ https://www.ncbi.nlm.nih.gov/pubmed/26161994 http://dx.doi.org/10.1371/journal.pone.0131300 |
work_keys_str_mv | AT erdospeterl approximatecountingofgraphicalrealizations AT kisssandorz approximatecountingofgraphicalrealizations AT miklosistvan approximatecountingofgraphicalrealizations AT soukuplajos approximatecountingofgraphicalrealizations |