Does a given a set of polyominoes tile some rectangle? We show that this problem is undecidable. In a different direction, we also consider tiling a cofinite subset of the plane. The tileability is undecidable for many variants of this problem. However, we present an algorithm for testing whether the complement of a finite region is tileable by a set of rectangles.
Tiling planar regions with dominoes is a classical problem, where the decision and counting problems are polynomial. We prove a variety of hardness results (both NP- and #P-completeness) for different generalizations of dominoes in three and higher dimensions.Download .pdf file of the paper (best printed in color).
In [BNRR], it was shown that tiling of general regions with two rectangles is NP-complete, except for few trivial special cases. In a different direction, Rémila [Rem2] showed that for simply connected regions and two rectangles, the tileability can be solved in quadratic time (in the area). We prove that there is a finite set of at most 106 rectangles for which the tileability problem of simply connected regions is NP-complete, closing the gap between positive and negative results in the field. We also prove that counting such rectangular tilings is #P-complete, a first result of this kind.Download .pdf file of the color optimized version of the paper.
Download .pdf file of the monochromatic printer optimized version. It is still in color, and if your shape perception is better than your color perception, use this one.
A hypertournament, or a k-tournament, on n vertices, 2 ≤ k ≤ n, is a pair T = (V, E), where the vertex set V is a set of size n and the edge set E is the collection of all possible subsets of size k of V, called the edges, each taken in one of its k! possible permutations. A k-tournament is vertex-pancyclic if each vertex is contained in (directed) cycles of all possible lengths. A k-tournament is strong if there is a path from u to v for each pair of distinct vertices u and v. We examine the question posed by Gutin and Yeo about the characterization of vertex-pancyclic hypertournaments. We utilize the majority digraph to reduce a k-tournament to an ordinary tournament (2-tournament). We employ this method to extend Moon's theorem (a tournament is vertex-pancyclic if and only if it is strong) to hypertournaments. We prove that for a k-tournament on n vertices, if k ≥ 8 and n ≥ k + 3, then it is vertex-pancyclic if and only if it is strong. The same conclusion holds if k ≥ 5 and n ≥ k + 4, or if k = 4 and n ≥ 11, or if k = 3 and n ≥ 15. We also find bounds for the generalized problem when we extend vertex-pancyclicity to require d edge-disjoint cycles of each possible length and extend strong connectivity to require d edge-disjoint paths between each pair of vertices. Our results include and extend that of Petrovic and Thomassen.