A counterexample to rapid mixing of the Ge-Stefankovic process

Leslie Ann Goldberg (University of Liverpool)
Mark Jerrum (Queen Mary, University of London)


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


  • 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

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.