A counterexample to rapid mixing of the Ge-Stefankovic process

DOI10.1214/ECP.V17-1712MaRDI QIDQ428729zbMATH OpenFDO

Authors Leslie Ann Goldberg, Mark Jerrum

Publication date 22 June 2012

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

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

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)

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.

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

Cited in

(8)

• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• The complexity of approximately counting stable matchings
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• 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)