A counterexample to rapid mixing of the Ge-Stefankovic process. (English) Zbl 1246.60094

Goldberg, Leslie Ann; Jerrum, Mark

Electron. Commun. Probab. 17, Paper No. 5, 6 p. (2012).

Summary: Q. Ge and D. Stefankovic [“A graph polynomial for independent sets of bipartite graphs”, in: K. Lodaya and M. Mahajan (eds.), IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), volume 8 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany. 240–250 (2010; doi:10.4230/LIPIcs.FSTTCS.2010.240)], recently introduced a Markov chain which, if rapidly mixing, would provide an efficient procedure 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)\), gives the 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 time is exponential in the size of the input when the input is chosen from a particular infinite family of bipartite graphs.

MSC:

60J10	Markov chains (discrete-time Markov processes on discrete state spaces)
05C31	Graph polynomials
05C69	Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Keywords:

Glauber dynamics; independent sets in graphs; Markov chains; mixing time; randomised algorithms