Hard tiling problems with simple tiles

DOI10.1007/S00454-001-0047-6MaRDI QIDQ5955147zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Cristopher Moore, John Michael Robson

Publication date 7 February 2002

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0003039

zbMATH Keywords

halting problemtilings

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: It is well-known that the question of whether a given finite region can be tiled with a given set of tiles is NP-complete. We show that the same is true for the right tromino and square tetromino on the square lattice, or for the right tromino alone. In the process, we show that Monotone 1-in-3 Satisfiability is NP-complete for planar cubic graphs. In higher dimensions, we show NP-completeness for the domino and straight tromino for general regions on the cubic lattice, and for simply-connected regions on the four-dimensional hypercubic lattice.

Recommendations

• The complexity of generalized domino tilings
• Complexity of tiling a polygon with trominoes or bars
• Hard and easy instances of L-tromino tilings
• Hard and easy instances of L-tromino tilings
• Tiling simply connected regions with rectangles

Cited in

(91)

• A covering problem that is easy for trees but \(\mathbf{NP}\)-complete for trivalent graphs
• The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree
• Graph coloring with cardinality constraints on the neighborhoods
• Variations of the maximum leaf spanning tree problem for bipartite graphs
• Tiling allowing rotations only
• Complexity of tile rotation problems
• Tile invariants: New horizons.
• Ribbon tile invariants from the signed area
• A short scientific biography of Maurice Nivat
• Critical vertices and edges in \(H\)-free graphs
• Not-all-equal and 1-in-degree decompositions: algorithmic complexity and applications
• Eulerian disjoint paths problem in grid graphs is NP-complete
• Tiling with bars and satisfaction of Boolean formulas
• The complexity of synthesizing \textsf{nop}-equipped Boolean Petri nets from \(g\)-bounded inputs
• Blocking total dominating sets via edge contractions
• Complexity and algorithms for neighbor-sum-2-distinguishing \(\{1,3\}\)-edge-weighting of graphs
• On the hardness of determining the irregularity strength of graphs
• Using edge contractions to reduce the semitotal domination number
• Positive planar satisfiability problems under 3-connectivity constraints
• The complexity of finding optimal subgraphs to represent spatial correlation
• The complexity of restricted star colouring
• The complexity of finding common partitions of genomes with predefined block sizes
• \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\)
• On minimizing the maximum color for the 1-2-3 conjecture
• On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem
• Reducing the domination number of graphs via edge contractions and vertex deletions
• The complexity of synthesizing elementary net systems relative to natural parameters
• Edge weights and vertex colours: minimizing sum count
• Tiling simply connected regions with rectangles
• Small polyomino packing
• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
• Complexity of tiling a polygon with trominoes or bars
• Connecting guards with minimum Steiner points inside simple polygons
• Complexity and algorithms for recognizing polar and monopolar graphs
• Hard coloring problems in low degree planar bipartite graphs
• Minimum entropy orientations
• On the algorithmic complexity of zero-sum edge-coloring
• An injective version of the 1-2-3 conjecture
• On the semi-proper orientations of graphs
• The complexity of binary matrix completion under diameter constraints
• The complexity of blocking (semi)total dominating sets with edge contractions
• Decomposing cubic graphs into connected subgraphs of size three
• Domino tatami covering is NP-complete
• Irregular polyomino tiling via integer programming with application in phased array antenna design
• Planar embeddings with small and uniform faces
• On the number of neighbors in normal tiling
• Fast domino tileability
• Approximation of the quadratic knapsack problem
• Maximizing Nash product social welfare in allocating indivisible goods
• A new mathematical model for tiling finite regions of the plane with polyominoes
• Strong partial clones and the time complexity of SAT problems
• scientific article; zbMATH DE number 3976339 (Why is no real title available?)
• scientific article; zbMATH DE number 4039295 (Why is no real title available?)
• Algorithmic complexity of proper labeling problems
• The complexity of generalized domino tilings
• Idiot-proof tiles
• A neural network approach to tiling problems
• scientific article; zbMATH DE number 1048047 (Why is no real title available?)
• A PTAS for the square tiling problem
• Narrowing down the hardness barrier of synthesizing elementary net systems
• The Complexity of Synthesis of b-Bounded Petri Nets
• Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues
• scientific article; zbMATH DE number 3894472 (Why is no real title available?)
• NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
• On the tileability of polygons with colored dominoes
• Hard and easy instances of L-tromino tilings
• Hard and easy instances of L-tromino tilings
• Obtaining a proportional allocation by deleting items
• Decomposing subcubic graphs into claws, paths or triangles
• Wang tiles: connectivity when tiling a plane
• Hardness Results for the Synthesis of b-bounded Petri Nets
• A notion of vertex equitability for proper labellings
• Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles
• On the \(d\)-claw vertex deletion problem
• Computational complexity of puzzles and related topics
• The complexity of iterated reversible computation
• Computational complexity of counting coincidences
• The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
• Adding direction constraints to the 1-2-3 conjecture
• Graphs whose vertices of degree at least 2 lie in a triangle
• Enumerating minimal defensive alliances
• Hardness transitions of star colouring and restricted star colouring
• Partitioning vertices of graphs into paths of the same length
• Multi-dimensional stable roommates in 2-dimensional Euclidean space
• Irregularity notions for digraphs
• On 1-2-3 conjecture-like problems in 2-edge-coloured graphs
• Binary matrix completion under diameter constraints
• The Euclidean k-matching problem is NP-hard
• Proper labellings of graphs with unlabellable edges
• Rectangular tileability and complementary tileability are undecidable
• Two-machine interval shop scheduling with time lags

This page was built for publication: Hard tiling problems with simple tiles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5955147)