Domino Tatami Covering is NP-complete
classification
💻 cs.CC
math.CO
keywords
coveringtatamidominodominoesgraphnp-completereductioncalled
read the original abstract
A covering with dominoes of a rectilinear region is called \emph{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 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.