Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A polyomino is a connected subset of $\mathbb{Z}^2$ - a set of squares joined along their edges such that the resulting form is connected (or, more shortly, a generalized form of Tetris cube). A polyomino can be easily thought of as graph with vertices being elements of $\mathbb{Z}^2$ and edges between two vertices of hamming distance 1 (i.e. with one coordinate equal and the other different by 1).

The Hamiltonian path/cycle problem is the problem of determining for a given graph whether it contains a path/cycle that visits every vertex exactly once. It is known to be NP-complete for general graphs and even for planar graphs. My question is whether it's still NP-complete when restricting the graphs to be polyominoes (and if it is NP-complete, how it is shown).

share|improve this question

1 Answer 1

up vote 7 down vote accepted

This problem (both the path version and the circuit version) was shown to be NP-complete by Itai, Papadimitriou and Szwarcfiter [IPS82] by a reduction from a special case of the Hamiltonian circuit problem for planar graphs.

[IPS82] Alon Itai, Christos H. Papadimitriou and Jayme Luiz Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11(4):676–686, 1982. http://dx.doi.org/10.1137/0211056

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.