We consider the problem of sampling simple paths between two given vertices in a planar graph and propose a natural Markov chain exploring such paths by means of “local” modifications. This chain can be tuned so that the probability of sampling a path depends on its length (for instance, output shorter paths with higher probability than longer ones). We show that this chain is always ergodic and thus it converges to the desired sampling distribution for any planar graph. While this chain is not rapidly mixing in general, we prove that a simple restricted variant is. The restricted chain samples paths on a 2D lattice which are monotone in the vertical direction. To the best of our knowledge, this is the first example of a rapidly mixing Markov chain for sampling simple paths with a probability that depends on their lengths.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Bordewich, M., Dyer, M.E.: Path coupling without contraction. J. Discrete Algorithms
5(2), 280–292 (2007)
Bordewich, M., Dyer, M.E., Karpinski, M.: Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Random Struct. Algorithms
32(3), 375–399 (2008)
Bubley, R.: Randomized Algorithms: Approximation, Generation, and Counting. Springer, Heidelberg (2011)
Diaconis, P., Holmes, S., Neal, R.M.: Analysis of a nonreversible Markov chain sampler. Ann. Appl. Probab.
10, 726–752 (2000)
Došlić, T.: Seven (lattice) paths to log-convexity. Acta Applicandae Math.
110(3), 1373–1392 (2010)
Dyer, M., Flaxman, A.D., Frieze, A.M., Vigoda, E.: Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Struct. Algorithms
29(4), 450–465 (2006)
Dyer, M., Frieze, A., Hayes, T.P., Vigoda, E.: Randomly coloring constant degree graphs. Random Struct. Algorithms
43(2), 181–200 (2013)
Dyer, M.E., Frieze, A.M.: Randomly coloring random graphs. Random Struct. Algorithms
36(3), 251–272 (2010)
Dyer, M.E., Greenhill, C.S.: On markov chains for independent sets. J. Algorithms
35(1), 17–49 (2000)
Greenberg, S., Pascoe, A., Randall, D.: Sampling biased lattice configurations using exponential metrics. In: SODA, pp. 76–85 (2009)
Hayes, T.P., Vera, J.C., Vigoda, E.: Randomly coloring planar graphs with fewer colors than the maximum degree. Random Struct. Algorithms
46(2), 29–44 (2014)
Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM
51(4), 671–697 (2004)
Jerrum, M., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci.
43, 169–188 (1986)