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.