# «The Complexity of Domino Tiling Problems Don Sheehy1 Advisor: Kevin Wayne Computer Science Department Princeton University Princeton, NJ 08544 ...»

The Complexity of Domino Tiling Problems

Don Sheehy1

Advisor: Kevin Wayne

Computer Science Department

Princeton University

Princeton, NJ 08544

January 3, 2005

1 E-mail: dsheehy@princeton.edu

Abstract

In this paper, we give a combinatorial formalization that describes a wide range of

related problems in the theory of tiling derived from the popular game of dominos.

We show that determining if a given ﬁnite region of the plane can be tiled with

a given set of dominos is NP-Complete. The new graph theoretical methods we introduce allow this result to be easily generalized to a variety of similar tiling problems. Several subproblems of the graph theoretical version of the problem are explored in depth. We then apply these methods to inﬁnite tiling problems to lay the foundation for a more general study of undecidable tiling problems.

Contents 1 Introduction 2 2 Previous Work 4 3 Finite Tiling Problems 6

3.1 Deﬁnitions and Formal Problem Statement............. 6

3.2 Standard Dominos in the Plane................... 8

3.3 Tiling Finite Graphs......................... 11 3.3.1 Combinatorial Methods and Bigger Dominos....... 11 3.3.2 Unconnected Regions................... 13

3.4 Restriction to the Plane....................... 15

3.5 A Generalized Notion of Tile Colors................ 16 4 Inﬁnite Tiling Problems 17

4.1 Local and Global Symmetry.................... 17

4.2 Building an Inﬁnite Graph from a Single Tile........... 18 4.2.1 Restricting Tile Symmetries................ 19 5 Conclusions 21 Chapter 1 Introduction Problems of tiling spaces abound in discrete and computatial geometry. In this paper we explore a subclass of these problems inspired by the popular game of dominos. One recalls that a domino is a ¾¢½ rectangle with two square faces, each bearing some number of dots or pits. Although many variants to this basic domino exist and numerous games can be played with dominos, a commonality among these games is that when two domino tiles are placed adjacent to each other, the numbers on the corresponding faces should correspond. Some domino variants use colors on the tile faces rather than numbers. For the purpose of describing problems and results, it is clearer to refer to the color of the face so we will adopt this convention for the rest of this paper.

Tiling problems have been studied by computer scientists since the 1960’s when Hao Wang [13] conjectured in 1961 that a set of -way dominos (now known universally as Wang tiles, see Figure 2.1) can tile the entire plane if and only if it can tile the plane periodically (i.e. in a pattern that repeates in two different directions). His corollary to this conjecture was that the decision problem of determining whether or not a given set of Wang tiles can tile the plane was decidable.

In 1966, Berger [2] disproved the conjecture and showed how a Turing Machine could be simulated by a tiling of the plane. This result established the link between questions of computational complexity and tiling problems.

Also of interest to computer scientists are tiling problems involving the tiling of ﬁnite regions of the plane. The Jigsaw Puzzle Problem, the Monkey Puzzle problem and many other similar problems are known to be NP-Complete [8].

Also in the class of ﬁnite tiling problems are Polyomino problems, a rich and well-studied area of research (see [6]). Polyominos are tiles formed by gluing together unit squares edge to edge. For example, the -polyominos or tetrominos are familiar to many as the shapes from the video game Tetris. In general, polyominos do not have colored faces or the corresponding adjacency restriction so they come up only as a subproblem of the work presented here in which the number of colors is exactly one.

In this paper we start by looking at a speciﬁc problem of tiling ﬁnite regions with ¾ ¢ ½ dominos and settle the question posed by Watson and Worman [14] by proving the problem to be NP-Complete. First we show how to extend previous methods [14] to achieve this result, but then we shift our perspective to recast the problem combinatorially rather than geometrically. The main insight is that domino tiling problems contain two problems: a geometric problem, i.e. can a certain shape tile a certain space; and a combinatorial problem, i.e. can the tiles be rearranged to satisfy the adjacent color restriction. Work in polyominos has shown that the former is often NP-Complete. We show that even in cases where the geometric problem is tractable, the combinatorial problem remains NP-Complete.

The focus on the combinatorial aspect of the problem over the geometric aspect marks a departure from the standard methods for proving hardness results for such problems.

In Chapter 2 we summarize relevant results from previous work done on related tiling problems. Chapter 3 explores a particular domino tiling problem and gives a graph theoretical generalization that extends results to other types of tiling problems. We consider the geometric problem as a subproblem of a purely combinatorial graph partitioning problem and derive NP-Completeness results independent of the geometry. Chapter 4 extends the methods of Chapter 3 to explore inﬁnite tiling problems. We focus on the problem of modelling tiling problems with symmetry restrictions on the tiles. That is, problems in which the tiles can be ﬂipped and rotated only according to certain rules. We also show how the local symmetry restrictions on the tiles is linked to the gloabal symmetry of the tilings that can be achieved and also to the decidability of the domino problem in its different manifestations. Finally, Chapter 5 is a summary of our conclusions along with discussion and some problems that remain open.

Chapter 2 Previous Work As noted previously, much work in domino tiling problems started with Wang [13] and the Wang Tile (see Figure 2.1). Berger’s proof of the falsity of Wang’s conjecture implied the existence of sets of tiles that could tile the plane but could not be arranged to do so periodically [2]. Indeed, Berger showed that the problem of determining if a set of tiles yields a periodic tiling is undecidable. Berger demonstrated a set of tiles that yielded only aperiodic tilings of the plane. Unfortunately, his construction used 20,426 tiles. This result was simpliﬁed in 1971 by Robinson [12]. Culik [4] constructed an aperiodic set of only 13 Wang tiles. Note that these aperiodic tile sets are not undecidable because they have been proven to tile the plane. However, all undecidable tile sets will be aperiodic.

The problem of determining whether a set of Wang tiles can tile some ﬁnite region is known to be NP-Complete. In 2004, Watson and Worman [14] showed that determining if a set of dominos can tile a ﬁnite region is NP-Complete if an adversary is allowed to ﬁx certain tiles in advance (the proof that the general version of this problem is NP-Complete is presented in Chapter 3).

In 1987 Grunbaum and Shephard [7] published Tilings and Patterns which surveys the entire scope of geometric tiling knowledge at that time and also presented numerous unpublished results. They note the lack of strong formal methods for attacking these problems. Since their writing several methods have been proposed. Radin [11] describes how aperiodic tilings can be described using Ergodic Theory. Conway introduced Algebraic techniques including the theory of tiling groups to give short certiﬁcates of non-tilability for polyomino problems (see [6] for a thorough survey of polyomino problems).

Recently tilings have found applications in the self-assembly of nanostructures (see [1]). Also, aperiodic Wang tilings are used to create nonrepeating images and texture maps for computer graphics (see [3]).

Remark. The term Domino Tiling Problem has been introduced several times in the literature to describe different problems. Wang used the term to describe what we now refer to as the Wang Tiling Problem. Watson and Worman use the term to describe the problem of tiling a space with the more common conception of a domino as a ¾ ¢ ½ rectangle. The term is also sometimes used to refer to the classical #P-Complete problem of counting the number of ways to tile a space with ¾ ¢ ½ rectangles that is well-studied for its relation to statistical mechanics.

Chapter 3 Finite Tiling Problems

3.1 Deﬁnitions and Formal Problem Statement In the game of Dominos, the tiles in play are said to form the layout. Consequently, the term layout is sometimes used to denote the region to be tiled by the dominos. In some contexts, the term implies that the region to be tiled is the outline of some collection of dominos and the places where a domino can be placed within the region are prescribed. That is, there are only ﬁnitely many, nonoverlapping places where a domino can be placed (see Figure 3.1). In posing the Domino Tiling Problem, Watson and Worman [14] used this deﬁnition. In this paper, we will use the term layout to denote the region to be tiled but we abandon the added implication that the places where dominos can be placed within the layout is ﬁxed in advance. Instead, we show that the hardness of the problem is independent of that condition and that the problem remains NP-Complete regardless of whether or not the layout contains information about the placement of dominos.

Ultimately, our goal will be to address these tiling problems as graph theoretical questions but many of our results will model geometric tilings so it is helpful to start with a geometric deﬁnition of a tiling in Ê ¾.

Deﬁnition 3.1.1. Geometric Deifnition of Tiling. A tiling of a region Ê is a decomposition of Ê into a countable number of subsets Ë ½ ËÒ where the interiors of the Ë ’s are disjoint and simply connected.

To rephrase this problem graph theoretically, it is ﬁrst necessary to replace the plane Ê ¾ with a graph. We will require dominos to align edge to edge and vertex to vertex so we can imagine each domino occupying two adjacent cells of the integer

** Figure 3.1: (a) A layout that is simply a region of the plane and (b) a layout that includes information about the placement of the tiles.**

lattice ¾. So, we replace regions of the plane with subgraphs of the planar dual of the integer lattice. We will use the term layout and layout graph interchangeably to refer to this graph. We can now formally deﬁne the set of dominos and a tiling as graph theoretical notions.

Deﬁnition 3.1.2. The set of dominos is a collection of isomorphic graphs with vertices assigned colors from a ﬁnite set. We will denote the union of vertices (edges respectively) in all of the graphs in by Î ´ µ ( ´ µ respectively), and we denote the color of a vertex Ú by ´Úµ. We use the term n-domino to refer to a domino with Ò vertices.

We now see that the ¾ ¢ ½ dominos that we are dealing with would each be represented by a pair of vertices connected by a single edge in the domino set. If an edge in a graph is incident to two vertices of the same color, we say that it is monochromatic.

monochromatic. That is, if Ì´ÙµÌ´Úµ is an edge in but ÙÚ is not an edge in then Ù and Ú must be the same color.

It is not hard to see that the formal deﬁnition above corresponds to the intuitive notion of how we expect a domino tiling to behave. Adjacent faces are either part of the same domino or they are the same color.

** Problem 3.1.**

4. The Domio Tiling Problem INSTANCE: A ﬁnite domino set and a layout graph.

QUESTION: Does there exist a tiling of with ?

3.2 Standard Dominos in the Plane A domino in the graph theoretical model of the Domino Tiling Problem is just a pair of vertices connected by a single edge. So, the tiling is just a perfect matching with an added restriction that edges not in the matching be monochromatic. Variants of this problems that deﬁne the layout to include the locations of domoinos effectively choose the perfect matching in advance. We will show that this distinction does nbot affect the hardness of the problem. The following simple lemma is useful.

has a perfect matching Å ** Lemma 3.2.**

1. Let the graph ´Î µ be a tree. If then Å is the only perfect matching in.

Proof. We proceed by induction on Î. Trivially, if Î ¾ then there is only one edge and it constitutes the unique perfect matching on. Assume the statement holds Î. Suppose Î and has a perfect matching Å. Pick a leaf vertex Ú adjacent to a vertex Ù. The edge ÙÚ is the only edge adjacent to Ú so it is in Å. By induction Å Ò ÙÚ is the unique perfect matching on Ò Ù Ú. So Å is unique.

We will show that the Domino Tiling Problem is NP-Complete even when the layout graph is a tree. Thus, Lemma 3.2.1 implies that it doesn’t matter if we are given the matching in advance because there is at most one perfect matching and it can be found in polynomial time. If no perfect matching exists then trivially, there does not exist a tiling. If a color only appears on one vertex of one domino then that vertex must necessarily be mapped to a leaf vertex of the layout. This simple fact will be very helpful later so we state it formally below.

** Lemma 3.2.**

2. If there exists some vertex Ú ¾ Î ´ µ such that for all Ù Ú¾ Î ´ µ ´Ùµ ´Úµ then any tiling of a layout with maps Ú to a vertex of degree at most one.

Watson and Worman [14] constructed a solver for 3,4-SAT out of dominos under the restriction that an adversary could ﬁx certain tiles in advance. We prove that the reduction can still be performed without the adversary given only a polynomial increase in the size of the problem instance. Our purpose here is not to explain the exact workings of their construction but we will need to describe at least what it looks like in order to give an understanding of how to extend their methods and prove the general version of the problem they posed.

** Figure 3.2: (a) The variable gizmo used in the Watson and Worman construction and (b) a modiﬁcation that achieves maximum vertex degree 3.**