Domino Tatami Tiling is NP-Complete
Alejandro Erickson,
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
A covering with dominoes of a rectilinear region is called
tatami if no four dominoes meet at any point. We describe a
reduction from planar 3SAT to Domino Tatami Covering. As a
consequence it is therefore NP-complete to decide whether there is a
perfect matching of a graph that meets every 4-cycle, even if the
graph is restricted to be an induced subgraph of the grid-graph.
The gadgets used in the reduction were discovered with the help of a
SAT-solver.
The shape below is an rectilnear region (with holes).
It has been tatami tiled with dimers. Other rectilear regions can not
be tatami tiled with dimers. In this paper we show that the decision
problem is NP-complete.
Here's an illustration from the paper of an example of the reduction.
-
Download: pdf file (not yet).
-
A earlier (slightly) version is on the arXiv:
arxiv.org/pdf/1305.6669.
-
Presented at IWOCA 2013, International Workshop on Combinatorial Algorithms,
Rouen, France, July 10-12, 2013.
-
Here is Alejandro's talk on the paper at IWOCA:
IWOCA.pdf.
-
Appears in LNCS 8288, pp. 140-149, 2013.
-
Please send me a note if
you download one of these files.
It's always nice to know who's reading your papers.
-
Selected citations:
Back to list of publications.
