The complexity of domino tiling.
Thérèse Biedl · 2005
In this paper, we study the problem of how to tile a layout with dominoes. For non-coloured dominoes, this can be determined easily by testing whether the layout graph has a perfect matching. We study here tiling with coloured dominoes, where colours of adjacent dominoes must match. It was known that this problem is NP-hard when the layout graph is a tree. We first strengthen this NP-hardness result in two ways: (1) we can use a path instead of a tree, or (2) we can force that exactly all given dominoes are used. However, both these reductions (as well as the existing one) use an unbounded numbers of colours, which is not realistic for domino tiling. As our main interest, we hence study domino tiling with a constant number of colours. We show that this is NP-hard even with 3 colours. 1