7
$\begingroup$

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).

$\endgroup$

1 Answer 1

10
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .