Packing trominoes is np-complete, #p-complete and asp-complete

Takashi Horiyama; Takehiro Ito; Keita Nakatsuka; Akira Suzuki; Ryuhei Uehara

Packing trominoes is np-complete, #p-complete and asp-complete

Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, Ryuhei Uehara

INF - System Information Sciences

Research output: Contribution to conference › Paper › peer-review

3 Citations (Scopus)

Abstract

We study the computational complexity of packing puzzles of identical polyominoes. Packing dominoes (i.e., 1 × 2 rectangles) into grid polygons can be solved in polynomial time by reducing to a bipartite matching problem. On the other hand, packing 2 × 2 squares is known to be NP-complete. In this paper, we fill the gap between dominoes and 2 × 2 squares, that is, we consider the packing puzzles of trominoes. Note that there exist only two shapes of trominoes: L-shape and I-shape. We show that their packing problems are both NP-complete. Our reductions are carefully designed so that we can also prove #P-completeness and ASPcompleteness of the counting and the another- solutionproblem variants, respectively.

Original language	English
Pages	211-216
Number of pages	6
Publication status	Published - 2012
Event	24th Canadian Conference on Computational Geometry, CCCG 2012 - Charlottetown, PE, Canada Duration: 2012 Aug 8 → 2012 Aug 10

Conference

Conference	24th Canadian Conference on Computational Geometry, CCCG 2012
Country/Territory	Canada
City	Charlottetown, PE
Period	12/8/8 → 12/8/10

Cite this

@conference{10abc58279094627a7a7ecc891c0adf0,

title = "Packing trominoes is np-complete, #p-complete and asp-complete",

abstract = "We study the computational complexity of packing puzzles of identical polyominoes. Packing dominoes (i.e., 1 × 2 rectangles) into grid polygons can be solved in polynomial time by reducing to a bipartite matching problem. On the other hand, packing 2 × 2 squares is known to be NP-complete. In this paper, we fill the gap between dominoes and 2 × 2 squares, that is, we consider the packing puzzles of trominoes. Note that there exist only two shapes of trominoes: L-shape and I-shape. We show that their packing problems are both NP-complete. Our reductions are carefully designed so that we can also prove #P-completeness and ASPcompleteness of the counting and the another- solutionproblem variants, respectively.",

author = "Takashi Horiyama and Takehiro Ito and Keita Nakatsuka and Akira Suzuki and Ryuhei Uehara",

year = "2012",

language = "English",

pages = "211--216",

note = "24th Canadian Conference on Computational Geometry, CCCG 2012 ; Conference date: 08-08-2012 Through 10-08-2012",

}

TY - CONF

T1 - Packing trominoes is np-complete, #p-complete and asp-complete

AU - Horiyama, Takashi

AU - Ito, Takehiro

AU - Nakatsuka, Keita

AU - Suzuki, Akira

AU - Uehara, Ryuhei

PY - 2012

Y1 - 2012

N2 - We study the computational complexity of packing puzzles of identical polyominoes. Packing dominoes (i.e., 1 × 2 rectangles) into grid polygons can be solved in polynomial time by reducing to a bipartite matching problem. On the other hand, packing 2 × 2 squares is known to be NP-complete. In this paper, we fill the gap between dominoes and 2 × 2 squares, that is, we consider the packing puzzles of trominoes. Note that there exist only two shapes of trominoes: L-shape and I-shape. We show that their packing problems are both NP-complete. Our reductions are carefully designed so that we can also prove #P-completeness and ASPcompleteness of the counting and the another- solutionproblem variants, respectively.

AB - We study the computational complexity of packing puzzles of identical polyominoes. Packing dominoes (i.e., 1 × 2 rectangles) into grid polygons can be solved in polynomial time by reducing to a bipartite matching problem. On the other hand, packing 2 × 2 squares is known to be NP-complete. In this paper, we fill the gap between dominoes and 2 × 2 squares, that is, we consider the packing puzzles of trominoes. Note that there exist only two shapes of trominoes: L-shape and I-shape. We show that their packing problems are both NP-complete. Our reductions are carefully designed so that we can also prove #P-completeness and ASPcompleteness of the counting and the another- solutionproblem variants, respectively.

UR - http://www.scopus.com/inward/record.url?scp=84883037465&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883037465&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:84883037465

SP - 211

EP - 216

T2 - 24th Canadian Conference on Computational Geometry, CCCG 2012

Y2 - 8 August 2012 through 10 August 2012

ER -

Packing trominoes is np-complete, #p-complete and asp-complete

Abstract

Conference

Other files and links

Fingerprint

Cite this