A counterexample to rapid mixing of the Ge-Stefankovic process

DOI10.1214/ECP.V17-1712zbMATH Open1246.60094arXiv1109.5242MaRDI QIDQ428729FDOQ428729

Authors: Leslie Ann Goldberg, Mark Jerrum 

Publication date: 22 June 2012

Published in: Electronic Communications in Probability (Search for Journal in Brave)

Abstract: Ge and Stefankovic have recently introduced a novel two-variable graph polynomial. When specialised to a bipartite graphs G and evaluated at the point (1/2,1) this polynomial gives the number of independent sets in the graph. Inspired by this polynomial, they also introduced a Markov chain which, if rapidly mixing, would provide an efficient sampling procedure for independent sets in G. This sampling procedure in turn would imply the existence of efficient approximation algorithms for a number of significant counting problems whose complexity is so far unresolved. The proposed Markov chain is promising, in the sense that it overcomes the most obvious barrier to mixing. However, we show here, by exhibiting a sequence of counterexamples, that the mixing time of their Markov chain is exponential in the size of the input when the input is chosen from a particular infinite family of bipartite graphs.

Full work available at URL: https://arxiv.org/abs/1109.5242

Recommendations

• A graph polynomial for independent sets of bipartite graphs
• On Counting Independent Sets in Sparse Graphs
• Publication:4952677
• On Markov Chains for Independent Sets
• Approximate counting, uniform generation and rapidly mixing Markov chains

zbMATH Keywords

Markov chainsmixing timeGlauber dynamicsindependent sets in graphsrandomised algorithms

Mathematics Subject Classification ID

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

Cited In (8)

• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• The complexity of approximately counting stable matchings
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• An improvement of the mixing rates in a counter-example to the weak invariance principle
• A graph polynomial for independent sets of bipartite graphs
• Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard
• Counting independent sets in graphs with bounded bipartite pathwidth

This page was built for publication: A counterexample to rapid mixing of the Ge-Stefankovic process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428729)