Abstract
We consider the importance of the choice of metric in path coupling, and its relationship to the technique of path coupling with stopping times. We provide strong evidence that the stopping time method is no more powerful than standard path coupling using a carefully chosen metric. However, the stopping time approach does give insight into the design of good metrics for specific problems. We give illustrative applications, to sampling independent sets in hypergraphs, and to sampling colourings of hypergraphs and bipartite graphs.
Joint work with Magnus Bordewich and Marek Karpinski