Counting Hamiltonian cycles in bipartite graphs

Haanpää, Harri; Östergård, Patric

doi:10.1090/S0025-5718-2013-02741-X

Counting Hamiltonian cycles in bipartite graphs
HTML articles powered by AMS MathViewer

by Harri Haanpää and Patric R. J. Östergård PDF

Math. Comp. 83 (2014), 979-995 Request permission

Abstract:

A method for counting Hamiltonian cycles in bipartite graphs is developed with the main focus on the long-standing open case of the 6-cube.

Dynamic programming as well as utilization of the automorphism group of the graph are central ingredients of the method. It is further shown how the number of equivalence classes of Hamiltonian cycles can be obtained via a classification of Hamiltonian cycles with nontrivial automorphisms. It turns out that the 6-cube

has 35 838 213 722 570 883 870 720

Hamiltonian cycles and 777 739 016 577 752 714

equivalence classes of Hamiltonian cycles. The old result on the number of knight’s tours on a $8\times 8$ chessboard is confirmed.

References

A. Bell and P. Hallowell, Crawling round a cube edge, Computing (U.K.) (Feb. 1973), 9.
Nicos Christofides, Graph theory, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1975. An algorithmic approach. MR 0429612
Clay Culver and David Leach, Equivalence classes of 5-bit Gray codes, Australas. J. Combin. 39 (2007), 129–134. MR 2351193
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to algorithms, 3rd ed., MIT Press, Cambridge, MA, 2009. MR 2572804
Italo J. Dejter and Abel A. Delgado, Classes of Hamilton cycles in the 5-cube, J. Combin. Math. Combin. Comput. 61 (2007), 81–95. MR 2322204
M. Deza and R. Shklyar, Enumeration of Hamiltonian cycles in 6-cube, arXiv:1003.4391v1, 2010.
Jiří Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Combin. Theory Ser. B 97 (2007), no. 6, 1074–1076. MR 2354719, DOI 10.1016/j.jctb.2007.02.007
M. Gardner, Mathematical Games, Scientific American 227(2) (Aug. 1972), 106–109.
Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
E. N. Gilbert, Gray codes and paths on the $n$-cube, Bell System Tech. J. 37 (1958), 815–826. MR 94273, DOI 10.1002/j.1538-7305.1958.tb03887.x
Frank Harary, John P. Hayes, and Horng-Jyh Wu, A survey of the theory of hypercube graphs, Comput. Math. Appl. 15 (1988), no. 4, 277–289. MR 949280, DOI 10.1016/0898-1221(88)90213-1
Alexander Hulpke, Petteri Kaski, and Patric R. J. Östergård, The number of Latin squares of order 11, Math. Comp. 80 (2011), no. 274, 1197–1219. MR 2772119, DOI 10.1090/S0025-5718-2010-02420-2
Petteri Kaski, Isomorph-free exhaustive generation of designs with prescribed groups of automorphisms, SIAM J. Discrete Math. 19 (2005), no. 3, 664–690. MR 2191287, DOI 10.1137/S0895480104444788
Petteri Kaski and Patric R. J. Östergård, Classification algorithms for codes and designs, Algorithms and Computation in Mathematics, vol. 15, Springer-Verlag, Berlin, 2006. With 1 DVD-ROM (Windows, Macintosh and UNIX). MR 2192256
P. Kaski and O. Pottonen, libexact user’s guide, version 1.0, HIIT Technical Reports 2008-1, Helsinki Institute for Information Technology HIIT, 2008.
Donald E. Knuth, The art of computer programming. Vol. 4, Fasc. 2, Addison-Wesley, Upper Saddle River, NJ, 2005. Generating all tuples and permutations. MR 2251595
Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
Donald E. Knuth, Selected papers on fun & games, CSLI Lecture Notes, vol. 192, CSLI Publications, Stanford, CA, 2011. MR 2905906
William Kocay, An extension of the multi-path algorithm for finding Hamilton cycles, Discrete Math. 101 (1992), no. 1-3, 171–188. Special volume to mark the centennial of Julius Petersen’s “Die Theorie der regulären Graphs”, Part II. MR 1172376, DOI 10.1016/0012-365X(92)90601-B
William Kocay and Donald L. Kreher, Graphs, algorithms, and optimization, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2005. MR 2106632
D. L. Kreher and D. R. Stinson, Combinatorial algorithms: Generation, enumeration, and search, CRC Press, Boca Raton, 1999.
Martin Loebbing and Ingo Wegener, Comments on: “The number of knight’s tours equals 33,439,123,484,294—counting with binary decision diagrams” [Electron. J. Combin. 3 (1996), no. 1, Research Paper 5, approx. 4 pp. (electronic); 1 368 332], Electron. J. Combin. 3 (1996), no. 1, Research Paper 5, Comment 1, 1 HTML document. MR 1715429
S. Martello, Algorithm 595: An enumerative algorithm for finding Hamiltonian circuits in a directed graph, ACM Trans. Math. Software 9 (1983), 131–138.
B. D. McKay, nauty user’s guide (version 1.5), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, Canberra, 1990.
B. D. McKay, Knight’s tours of an $8 \times 8$ chessboard, Technical Report TR-CS-97-03, Computer Science Department, Australian National University, Canberra, 1997.
Brendan D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998), no. 2, 306–324. MR 1606516, DOI 10.1006/jagm.1997.0898
Frank Rubin, A search procedure for Hamilton paths and circuits, J. Assoc. Comput. Mach. 21 (1974), 576–580. MR 349480, DOI 10.1145/321850.321854
Jefferey A. Shufelt and Hans J. Berliner, Generating Hamiltonian circuits without backtracking from errors, Theoret. Comput. Sci. 132 (1994), no. 1-2, 347–375. MR 1290549, DOI 10.1016/0304-3975(94)90239-9
Jerry Silverman, Virgil E. Vickers, and John L. Sampson, Statistical estimates of the $n$-bit Gray codes by restricted random generation of permutations of $1$ to $2^{n}$, IEEE Trans. Inform. Theory 29 (1983), no. 6, 894–901. MR 733197, DOI 10.1109/TIT.1983.1056755
Takeaki Uno, A fast algorithm for enumerating bipartite perfect matchings, Algorithms and computation (Christchurch, 2001) Lecture Notes in Comput. Sci., vol. 2223, Springer, Berlin, 2001, pp. 367–379. MR 1917757, DOI 10.1007/3-540-45678-3_{3}2
Leslie G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8 (1979), no. 3, 410–421. MR 539258, DOI 10.1137/0208032
B. Vandegriend, Finding Hamiltonian Cycles: Algorithms, Graphs and Performance, M.Sc. thesis, Department of Computing Science, University of Alberta, Edmonton, 1998.
Douglas B. West, Introduction to graph theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996. MR 1367739
S. Winker to M. Gardner, 31 October 1972, Guide to the Martin Gardner Papers, Department of Special Collections, Stanford University Libraries, Stanford.