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

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.

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.

DOI: 10.5802/afst.1469
Martin Dyer 1; Haiko Müller 1

1 School of Computing, University of Leeds, Leeds, LS2 9JT, UK.
     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, Institut de Math\'ematiques},
     address = {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/}
AU  - Martin Dyer
AU  - Haiko Müller
TI  - Graph classes and the switch Markov chain for matchings
JO  - Annales de la Faculté des sciences de Toulouse : Mathématiques
PY  - 2015
SP  - 885
EP  - 933
VL  - 24
IS  - 4
PB  - Université Paul Sabatier, Institut de Mathématiques
PP  - Toulouse
UR  - https://afst.centre-mersenne.org/articles/10.5802/afst.1469/
DO  - 10.5802/afst.1469
LA  - en
ID  - AFST_2015_6_24_4_885_0
ER  - 
%0 Journal Article
%A Martin Dyer
%A Haiko Müller
%T Graph classes and the switch Markov chain for matchings
%J Annales de la Faculté des sciences de Toulouse : Mathématiques
%D 2015
%P 885-933
%V 24
%N 4
%I Université Paul Sabatier, Institut de Mathématiques
%C Toulouse
%U https://afst.centre-mersenne.org/articles/10.5802/afst.1469/
%R 10.5802/afst.1469
%G en
%F AFST_2015_6_24_4_885_0
Martin Dyer; Haiko Müller. Graph classes and the switch Markov chain for matchings. Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 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. http://www.stat.berkeley.edu/~aldous/RWG/book.html. 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 | Zbl

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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

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

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

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

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

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

[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 | Zbl

[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 | Zbl

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

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

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

Cited by Sources: