WWW.ABSTRACT.DISLIB.INFO FREE ELECTRONIC LIBRARY - Abstracts, online materials

<< HOME
CONTACTS

Pages:   || 2 | 3 |

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

-- [ Page 1 ] --

The Complexity of Domino Tiling Problems

Don Sheehy1

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.

Pages:   || 2 | 3 |

Similar works:

«PEP Basics Manual Analytical Solutions Group Callan Associates Inc. 600 Montgomery Street, Suite 800 San Francisco, CA 94111 Phone: 415.974.5060 PEP Overview and Background Callan Associates’ PEP software application was originally created for our Manager Search, Quantitative Consulting and Performance Measurement Groups. As each group utilized PEP in their analysis and presentations, requests for additional functionality were gathered and the program has evolved with the demands of the...»

«OVERSEER®: ACCURACY, PRECISION, ERROR AND UNCERTAINTY Mark Shepherd, David Wheeler, Diana Selbie, Laura Buckthought & Mike Freeman AgResearch Ltd, Ruakura Campus, Hamilton Summary When debating the performance of models such as Overseer‟s ability to estimate whole-farm nutrient losses, four terms are often used almost interchangeably: accuracy, precision, error and uncertainty. However, the terms are not interchangeable and it is important to consider the implications of the commonly used...»

«A Clockwork Orange: The Intersection Between a Dystopia and Human Nature By Samantha Moya An archetypal depiction of a dystopia is one dominated by bleakness and roboticism, a totalitarian government enforcing upon the people a lifestyle that lulls them into a state of obedience. Anthony Burgess’ 1963 novel, A Clockwork Orange, is a nightmarish vision of future Britain, one in which behavioral modification is taken to dangerous extremes in the quest for preserving the order of a disconnected...»

«Founded 1858 British Horological Institute The Practical Lubrication of Clocks and Watches © 2007 The British Horological Institute Limited This document may be printed for personal use only. Unauthorised reproduction is prohibited. BHI Ltd Upton Hall Upton Newark Nottinghamshire NG23 5TE The Practical Lubrication of Clocks and Watches Version 2007.0 The Practical Lubrication of Clocks and Watches Version 2007.0 The Practical Lubrication of Watches and Clocks Contents 1. Sources of information...»

«Kentucky’s Family Guide to Autism Spectrum Disorders Training. Support. Resources. It’s Happening Here. http://louisville.edu/education/kyautismtraining * Revised September Kentucky’s Family Guide to Autism Spectrum Disorders This guide was developed and written by parents of individuals with autism spectrum disorders. The examples provided are from their experiences. The information included in this manual is a result of their answer to the question: When your child was first diagnosed,...»

«Laws of in‐law languages Leipzig, 2.5.2015 Maarten Mous m.mous@hum.leidenuniv.nl 1 Intro Names and respect • naming parents / in‐laws  • name avoidance 1.1 Register of respect Datooga bride avoids name of father‐in‐law + But also the word it is based on And any other form of the word And any similar word For example: avoid Gida‐bung’eeda,  also Uda‐bung’eeda,  + bung’eeda ‘funeral’ + plural form + any word that begins...»

«2 Contents Contents Our School Governance School Council Corporate Structure Senior Secondary Outcomes 2013 ATARs Offers by Fields of Study and Institution NAPLAN Attendance Finance Staff Staff Qualifications Academic Staff Professional Staff Contact Information Principal: Ms Meg Hansen Council President: Mr David Horvath Williamstown Campus 67 The Strand NEWPORT VIC 3015 Australia Telephone 03 9731 9555 Facsimile 03 9731 9500 Truganina Campus 300 Sayers Road TRUGANINA VIC 3029 Australia...»

«INFN Thermal analysis of crate with motherboards, daughterboards and AM chips intermediate report Jan Bienstman Phone: +32 16 28 77 81 E-mail: Jan.Bienstman@imec.be IMEC, Kapeldreef 75 – B3001 Heverlee date : 14/10/2014 Version :01 © imec 2014 | www.cedm.be 1/22 INFN Thermal analysis of crate with motherboards, daughterboards and AM chips v01 Content Content 1. Modeling of the system 1.1. Used data for the model Crate Fan Motherboard Daughterboard AM chip 1.2. Hierarchical modeling 1.3....»

«Does Indiscriminate Violence Incite Insurgent Attacks? Evidence from a Natural Experiment∗ Jason Lyall† August 19, 2008 Abstract Does a state’s use of indiscriminate violence incite insurgent attacks? To date, nearly all existing theories and empirical studies have concluded that such violence is highly counterproductive because it creates new grievances while forcing victims to seek security, if not safety, in rebel arms. This proposition is tested using a natural experiment that draws...»

«TINKER AIR FORCE BASE BY ORDER OF THE COMMANDER INSTRUCTION 10-205 TINKER AIR FORCE BASE 25 FEBRUARY 2016 Certified Current On 5 May 2016 Operations EMERGENCY NOTIFICATION PROCEDURES COMPLIANCE WITH THIS PUBLICATION IS MANDATORY ACCESSIBILITY: Publications and forms are available for downloading or ordering on the Air Force e-publishing website at www.e-Publishing.af.mil RELEASABILITY: There are no releasability restrictions on this publication OPR: 72 ABW/XPX Certified by: 72 ABW/XP...»

«Programme opérationnel national du Fonds Social Européen 2014-2020 pour l’Emploi et l’Inclusion en Métropole. APPEL À PROJETS 2016 Appel à projets permanent CADRE D’INTERVENTION AXE PRIORITAIRE 3 « Lutter contre la pauvreté et promouvoir l’inclusion » Objectif Thématique 9 : « Promouvoir l’inclusion sociale et lutter contre la pauvreté et toute forme de discrimination » Priorité d’investissement 9.1 : « L’inclusion active y compris en vue de promouvoir l’égalité...»

«n° 006794-01 mars 2010 Les liaisons possibles entre Troyes et le réseau ferroviaire à grande vitesse MINISTÈRE DE L’ÉCOLOGIE, DE L’ÉNERGIE, DU DÉVELOPPEMENT DURABLE ET DE LA MER En charge des Technologies vertes et des Négociations sur le climat Conseil Général de l’Environnement et du Développement Durable Rapport n° 006794-01 LES LIAISONS POSSIBLES ENTRE TROYES ET LE RESEAU FERROVIAIRE A GRANDE VITESSE Par Claude Liebermann, Ingénieur général des Ponts et Chaussées Et...»

<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.