2013/05/29 by Alejandro Erickson, Erickson, Alejandro, Frank Ruskey +1
Computer Science · Mathematics · #05B40 #05B50 #68Q17 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Model-Driven Software Engineering Techniques #cs.CC #math.CO #msc:05B40 #msc:05B50 #msc:68Q17
paper · pdf · doi:10.48550/arxiv.1305.6669
10 pages, accepted at The International Workshop on Combinatorial Algorithms (IWOCA) 2013
arxiv created 2013/05/29 · openalex publication_date 2013/05/29 · arxiv updated 2013/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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.