logo AFST

Graph classes and the switch Markov chain for matchings
Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 24 (2015) no. 4, pp. 885-933.

Diaconis, Graham et Holmes [8] ont étudié les applications statistiques du comptage et de l’échantillonnage des appariements parfaits dans certaines classes de graphes. Ils ont proposé une chaîne de Markov simple, appelée ici la chaîne “switch”, pour engendrer aléatoirement un appariement presque uniforme pour les graphes appartenant à ces classes. Nous étudions ces classes en détail en les justifiant du point de vue de la théorie des graphes. Nous montrons que l’ergodicité des chaînes des classes de [8] se déduit de celle d’une classe plus large. Nous nous intéressons également à la complexité calculatoire du temps de mélange de la chaîne switch et nous la déterminons pour toutes les classes de [8] sauf une, celle correspondant aux graphes monotones de Diaconis, Graham et Holmes. Nous ébauchons une approche pour montrer une convergence en temps polynomial de la chaîne switch pour les graphes monotones. Elle dépend d’une conjecture intéressante mais non-prouvée concernant les cycles hamiltoniens des graphes monotones.

Diaconis, Graham and Holmes [8] studied the statistical applications of counting and sampling perfect matchings in certain classes of graphs. They proposed a simple Markov chain, called the switch chain here, to generate a matching almost uniformly at random for graphs in these classes. We examine these graph classes in detail, and show that they have a strong graph-theoretic rationale. We consider the ergodicity of the switch chain, and show that all the classes in [8] inherit their ergodicity from a larger class. We also study the computational complexity of the mixing time of the switch chain, and show that this has already been resolved for all but one of the classes in [8], that which Diaconis, Graham and Holmes called monotone graphs. We outline an approach to showing polynomial time convergence of the switch chain for monotone graphs. This is shown to rely upon an interesting, though unproven, conjecture concerning Hamilton cycles in monotone graphs.

     author = {Martin Dyer and Haiko M\"uller},
     title = {Graph classes and the switch {Markov} chain for matchings},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     pages = {885--933},
     publisher = {Universit\'e Paul Sabatier, Toulouse},
     volume = {Ser. 6, 24},
     number = {4},
     year = {2015},
     doi = {10.5802/afst.1469},
     zbl = {1337.60171},
     language = {en},
     url = {https://afst.centre-mersenne.org/articles/10.5802/afst.1469/}
Martin Dyer; Haiko Müller. Graph classes and the switch Markov chain for matchings. Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 24 (2015) no. 4, pp. 885-933. doi : 10.5802/afst.1469. https://afst.centre-mersenne.org/articles/10.5802/afst.1469/

[1] Aldous (D.) and Fill (J. A.).— Reversible Markov chains and random walks on graphs. 2002. . Unfinished monograph, recompiled 2014.

[2] Bezáková (I.), Stefankovic (D.), Vazirani (V. V.), and Vigoda (E.).— Accelerating simulated annealing for the permanent and combinatorial counting problems. SIAM Journal on Computing, 37(5), p. 1429-1454 (2008). | MR 2386275 | Zbl 1225.68270

[3] Blumberg (O.).— Permutations with interval restrictions. PhD thesis, Stanford University (2012).

[4] Booth (K. S.) and Lueker (G. S.).— Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13(3), p. 335-379 (1976). | MR 433962 | Zbl 0367.68034

[5] Brandstädt (A.), Le (V. B.), and Spinrad (J. P.).— Graph Classes: A Survey, volume 3 of Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999). | MR 1686154 | Zbl 0919.05001

[6] Coudert (D.), Huc (F.), and Sereni (J.-S.).— Pathwidth of outerplanar graphs. Journal of Graph Theory, 55(1), p. 27-41 (2007). | MR 2311993 | Zbl 1117.05101

[7] Courcelle (B.), Makowsky (J. A.), and Rotics (U.).— On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics, 108(1-2), p. 23-52 (2001). | MR 1804711 | Zbl 0972.05023

[8] Diaconis (P.), Graham (R.), and Holmes (S. P.).— Statistical problems involving permutations with restricted positions. In State of the art in probability and statistics, volume 36 of Lecture Notes-Monograph Series, p. 195-222. Institute of Mathematical Statistics (2001). | MR 1836562

[9] Dyer (M.).— Approximate counting by dynamic programming. In Proc. 35th Annual ACM Symposium on Theory of Computing, p. 693-699. ACM Press (2003). | MR 2120431 | Zbl 1192.90242

[10] Ellis (J.A.), Sudborough (I.H.), and Turner (J.S.).— The vertex separation and search number of a graph. Information and Computation, 113(1), p. 50-79 (1994). | MR 1283019 | Zbl 0942.68641

[11] Fomin (F.) and Bodlaender (H.).— Approximation of pathwidth of outerplanar graphs. In Andreas Brandstädt and VanBang Le, editors, Graph-Theoretic Concepts in Computer Science, volume 2204 of Lecture Notes in Computer Science, p. 166-176. Springer (2001). | MR 1905630 | Zbl 1042.68630

[12] Fürer (M.).— A natural generalization of bounded tree-width and bounded clique-width. CoRR, abs/1402.1810 (2014).

[13] Glover (F.).— Maximum matching in a convex bipartite graph. Naval Research Logistics Quarterly, 14(3), p. 313-316 (1967). | Zbl 0183.24501

[14] Golumbic (M. C.).— Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete Mathematics. North-Holland, Amsterdam (2004). | MR 2063679 | Zbl 1050.05002

[15] Gross (J.L.) and Yellen (J.).— Handbook of Graph Theory. CRC Press (2004). | MR 2035186 | Zbl 1278.05001

[16] Hanlon (P.).— A random walk on the rook placements on a Ferrer’s board. The Electronic Journal of Combinatorics, 3:R26 (1996). | MR 1392511 | Zbl 0851.05100

[17] Harvey (D. J.) and Wood (D. R.).— The treewidth of line graphs. Sep. 2014.

[18] Jerrum (M.).— Counting, sampling and integrating: algorithms and complexity. ETH Zürich Lectures in Mathematics. Birkhäuser, Basel (2003). | MR 1960003 | Zbl 1011.05001

[19] Jerrum (M.) and Sinclair (A.).— Approximating the permanent. SIAM Journal on Computing, 18(6), p. 1149-1178, December 1989. | MR 1025467 | Zbl 0723.05107

[20] Jerrum (M.), Sinclair (A.), and Vigoda (E.).— A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Journal of the ACM, 51, p. 671-697 (2004). | MR 2147852 | Zbl 1204.65044

[21] Jerrum (M.), Valiant (L.), and Vazirani (V.).— Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43, p. 169-188 (1986). | MR 855970 | Zbl 0597.68056

[22] Kinnersley (N. G.).— The vertex separation number of a graph equals its path-width. Information Processing Letters, 42(6), p. 345-350 (1992). | MR 1178214 | Zbl 0764.68121

[23] Köhler (E.).— Graphs without asteroidal triples. PhD thesis, Technische Universität Berlin (1999).

[24] Levin (D. A.), Peres (Y.), and Wilmer (E. L.).— Markov chains and mixing times. American Mathematical Society (2006). | MR 2466937 | Zbl 1160.60001

[25] Lubiw (A.).— Doubly lexical orderings of matrices. SIAM Journal on Computing, 16:854-879 (1987). | MR 908874 | Zbl 0622.05045

[26] Makedon (F.) and Sudborough (I. H.).— On minimizing width in linear layouts. Discrete Applied Mathematics, 23(3), p. 243-265 (1989). | MR 996137 | Zbl 0715.05012

[27] Matthews (J.).— Markov chains for sampling matchings. PhD thesis, Edinburgh University (2008).

[28] Okamoto (Y.), Uehara (R.), and Uno (T.).— Counting the number of matchings in chordal and chordal bipartite graph classes. In Graph-Theoretic Concepts in Computer Science, volume 5911 of Lecture Notes in Computer Science, p. 296-307. Springer (2010). | MR 2587720 | Zbl 1273.05180

[29] Robertson (N.) and Seymour (P. D.).— Graph minors I: Excluding a forest. Journal of Combinatorial Theory, Series B, 35(1), p. 39-61 (1983). | MR 723569 | Zbl 0521.05062

[30] Skodinis (K.).— Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time. Journal of Algorithms, 47(1), p. 40-59, April 2003. | MR 1978361 | Zbl 1053.68072

[31] Spinrad (J.).— Nonredundant 1’s in Γ-free matrices. SIAM J. Discrete Math., 8(2), p. 251-257 (1995). | MR 1329509 | Zbl 0837.05028

[32] Spinrad (J.), Brandstädt (A.), and Stewart (L.).— Bipartite permutation graphs. Discrete Applied Mathematics, 18(3), p. 279-292 (1987). | MR 917130 | Zbl 0628.05055

[33] Spinrad (J.P.).— Efficient Graph Representations.: The Fields Institute for Research in Mathematical Sciences. Fields Institute monographs. American Mathematical Soc. (2003). | MR 1971502 | Zbl 1033.05001

[34] Tucker (A.).— A structure theorem for the consecutive 1’s property. Journal of Combinatorial Theory, Series B, 12(2), p. 153-162 (1972). | MR 295938 | Zbl 0208.52402

[35] Uehara (R.).— Linear time algorithms on chordal bipartite and strongly chordal graphs. In Automata, Languages and Programming, 29th International Colloquium, p. 993-1004 (2002). | MR 2059850 | Zbl 1057.68654

[36] Valiant (L. G.).— The complexity of computing the permanent. Theoretical Computer Science, 8, p. 189-201 (1979). | MR 526203 | Zbl 0415.68008

[37] West (D. B.).— Introduction to Graph Theory. Prentice Hall, 2nd edition (2001). | MR 1367739 | Zbl 1121.05304

[38] Yannakakis (M.).— Computing the minimum fill-in is NP-complete. SIAM J. Alg. Disc. Meth., 2, p. 77-79 (1981). | MR 604513 | Zbl 0496.68033