A counterexample to rapid mixing of the Ge-Stefankovic process
Mark Jerrum (Queen Mary, University of London)
Abstract
Ge and Stefankovic have recently introduced a Markov chain which, if rapidly mixing, would provide an efficientprocedure for sampling independent sets in a bipartite graph. Such a procedure would be a breakthrough because it would give an efficient randomised algorithm for approximately counting independent sets in a bipartite graph, which would in turn imply the existence of efficient approximation algorithms for a number of significant counting problems whose computational complexity is so far unresolved. Their Markov chain is based on a novel two-variable graph polynomial which, when specialised to a bipartite graph, and evaluated at the point (1/2,1), givesthe number of independent sets in the graph. The Markov chain is promising, in the sense that it overcomes the most obvious barrier to rapid mixing. However, we show here, by exhibiting a sequence of counterexamples, that its mixing timeis exponential in the size of the input when the input is chosen from a particular infinite family of bipartite graphs.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 1-6
Publication Date: January 16, 2012
DOI: 10.1214/ECP.v17-1712
References
- Prasad Chebolu, Leslie~Ann Goldberg, and Russell Martin. The complexity of approximately counting stable matchings. In Proceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques, APPROX/RANDOM'10, pages 81--94, Berlin, Heidelberg, 2010. Springer-Verlag.
- Dyer, Martin; Frieze, Alan; Jerrum, Mark. On counting independent sets in sparse graphs. SIAM J. Comput. 31 (2002), no. 5, 1527--1541 (electronic). MR1936657
- Dyer, Martin; Goldberg, Leslie Ann; Greenhill, Catherine; Jerrum, Mark. The relative complexity of approximate counting problems. Approximation algorithms. Algorithmica 38 (2004), no. 3, 471--500. MR2044886
- Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Martin, Russell. Markov chain comparison. Probab. Surv. 3 (2006), 89--111 (electronic). MR2216963
- Qi~Ge and Daniel Stefankovic. A graph polynomial for independent sets of bipartite graphs. In Kamal Lodaya and Meena Mahajan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), volume~8 of Leibniz International Proceedings in Informatics (LIPIcs), pages 240--250, Dagstuhl, Germany, 2010.
- Goldberg, Leslie Ann; Jerrum, Mark. The complexity of ferromagnetic Ising with local fields. Combin. Probab. Comput. 16 (2007), no. 1, 43--61. MR2286511
- Jerrum, Mark. Counting, sampling and integrating: algorithms and complexity. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 2003. xii+112 pp. ISBN: 3-7643-6946-9 MR1960003
- Mitzenmacher, Michael; Upfal, Eli. Probability and computing. Randomized algorithms and probabilistic analysis. Cambridge University Press, Cambridge, 2005. xvi+352 pp. ISBN: 0-521-83540-2 MR2144605
- Mossel, Elchanan; Weitz, Dror; Wormald, Nicholas. On the hardness of sampling independent sets beyond the tree threshold. Probab. Theory Related Fields 143 (2009), no. 3-4, 401--439. MR2475668
- Motwani, Rajeev; Raghavan, Prabhakar. Randomized algorithms. Cambridge University Press, Cambridge, 1995. xiv+476 pp. ISBN: 0-521-47465-5 MR1344451
- Provan, J. Scott; Ball, Michael O. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12 (1983), no. 4, 777--788. MR0721012
This work is licensed under a Creative Commons Attribution 3.0 License.