A Counterexample to rapid mixing of the Ge-Stefankovic Process

Details A Counterexample to rapid mixing of the Ge-Stefankovic Process A Counterexample to rapid mixing of the Ge-Stefankovic Process

2011-09-24

arxiv.org/abs/1109.5242v1

Electronic Communications in Probability, 17 (2012) no. 5, 1-6

Mathematics

Probability

Scientific paper

10.1214/ECP.v17-1712

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.

Affiliated with

Also associated with

No associations

Rating

A Counterexample to rapid mixing of the Ge-Stefankovic Process does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Counterexample to rapid mixing of the Ge-Stefankovic Process, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Counterexample to rapid mixing of the Ge-Stefankovic Process will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-602430