On the exact complexity of polyomino packing

Hans L. Bodlaender, Tom C. Van Der Zanden

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
66 Downloads (Pure)


We show that the problem of deciding whether a collection of polyominoes, each fitting in a 2×O(log n) rectangle, can be packed into a 3×n box does not admit a 2o(n/log n)-time algorithm, unless the Exponential Time Hypothesis fails. We also give an algorithm that attains this lower bound, solving any instance of polyomino packing with total area n in 2O(n/logn) time. This establishes a tight bound on the complexity of Polyomino Packing, even in a very restricted case. In contrast, for a 2 × n box, we show that the problem can be solved in strongly subexponential time.

Original languageEnglish
Title of host publication9th International Conference on Fun with Algorithms, FUN 2018
EditorsH. Ito, S. Leonardi, L. Pagli, G. Prencipe
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages820
ISBN (Electronic)9783959770675
Publication statusPublished - 1 Jun 2018
Event9th International Conference on Fun with Algorithms (FUN 2018) - La Maddalena Island, Italy
Duration: 13 Jun 201815 Jun 2018
Conference number: 9

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
ISSN (Print)1868-8969


Conference9th International Conference on Fun with Algorithms (FUN 2018)
Abbreviated titleFUN 2018
CityLa Maddalena Island


  • Exact complexity
  • Exponential time hypothesis
  • Polyomino packing


Dive into the research topics of 'On the exact complexity of polyomino packing'. Together they form a unique fingerprint.

Cite this