Paper Info
Title
A Counterexample to rapid mixing of the Ge-Stefankovic Process
Abstract
Ge and Stefankovic have 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.
Year
DOI
Venue
2011
10.1214/ECP.v17-1712
ELECTRONIC COMMUNICATIONS IN PROBABILITY
Keywords
Field
DocType
Glauber dynamics,Independent sets in graphs,Markov chains,Mixing time,Randomised algorithms
Adjacency matrix,Discrete mathematics,Combinatorics,Line graph,Edge-transitive graph,Forbidden graph characterization,Bipartite graph,Matching (graph theory),Independent set,Voltage graph,Mathematics
Journal
Volume
ISSN
Citations 
17
1083-589X
4
PageRank 
References 
Authors
0.43
3
2
Name
Order
Citations
PageRank
leslie ann goldberg11411125.20
mark jerrum22755564.62