Aspects of a multivariate complexity analysis for Rectangle Tiling

We initiate a parameterized complexity study of the NP-hard problem to tile a positive integer matrix with rectangles, keeping the number of tiles and their maximum weight small. We show that the problem remains NP-hard even for binary matrices only using 1×1 and 2×2-squares as tiles and provide insight into the influence of naturally occurring parameters on the problem’s complexity.

► We identify very restricted cases of Rectangle Tiling that remain NP-hard. ► Tiling binary matrices with squares is NP-hard. ► We describe efficient algorithms when the number of rectangles is small. ► Research challenges for the parameterized complexity of Rectangle Tiling are listed.