Hard and Easy Instances of L-Tromino Tilings

October 12, 2017 · The Ethereal · 🏛 Workshop on Algorithms and Computation

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Javier T. Akagi, Carlos F. Gaona, Fabricio Mendoza, Manjil P. Saikia, Marcos Villagra arXiv ID 1710.04640 Category cs.CC: Computational Complexity Cross-listed cs.DS, math.CO Citations 5 Venue Workshop on Algorithms and Computation Last Checked 2 months ago

Abstract

We study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we identify restrictions to the problem where it either remains NP-complete or has a polynomial time algorithm. First, we characterize the possibility of when an Aztec rectangle and an Aztec diamond has an L-tromino tiling. Then, we study tilings of arbitrary regions where only $180^\circ$ rotations of L-trominoes are available. For this particular case we show that deciding the existence of a tiling remains NP-complete; yet, if a region does not contains certain so-called "forbidden polyominoes" as sub-regions, then there exists a polynomial time algorithm for deciding a tiling.