Towards a Classification of Hamiltonian cycles in the 6-cube

AUTHOR(S)

Yury Chebiryak, and Daniel Kroening

PUBLISHER

Journal on Satisfiability, Boolean Modeling and Computation, vol. 4, pp. 57-74, 2008.

LINKS

- a corrected version of this paper is available as technical report, ETH Zurich.
PDF download

Bibtex

@article{ck2008-jsat,
AUTHOR = { Chebiryak, Yury
and Kroening, Daniel},
TITLE = { Towards a classification of {Hamiltonian} cycles in the 6-cube},
JOURNAL = { Journal on Satisfiability, Boolean Modeling and Computation},
VOLUME = {4},
PAGES = {57--74},
YEAR = {2008},
ISSN = {1574-0617},
}

ABSTRACT

In this paper, we consider the problem of classifying Hamiltonian cycles in a binary hypercube. Previous work proposed a classification of these cycles using the edge representation, and presented it for dimension 4. We classify cycles in further two dimensions using a reduction to propositional SAT. The proposed algorithm starts with an over-approximation of the set of equivalence classes, which is then refined by queries to a SAT-solver to remove spurious cycles. This method performs up to three orders of magnitude faster than an enumeration with symmetry breaking in the 5-cube.

This work was supported in part by an ETH Research Grant TH-19 06-3 and by an award from IBM Research.