Counting Polyominoes, Revisited: Corrigendum and Addendum
Abstract
This is a Corrigendum and Addendum to Algorithmica paper (2026) 88:51.
- Journal ref
- Counting Polyominoes, Revisited. Algorithmica (2026) 88:51
- DOI
- 10.1007/s00453-026-01392-6
This is a Corrigendum and Addendum to Algorithmica paper (2026) 88:51.
Nearest neighbours by meaning across the whole index.
We present new results on polyomino nets that fold into four or five distinct boxes. With the help of AI, we first found examples with areas 532 and 2128, respectively. We analyze these examples and reduce their areas to 178 and 358, respectively. We also generalize the construction of the five-box net and show that infinitely many polyomino nets fold into five distinct boxes.
We present new results for polyomino nets that fold into 2 and 3 different cuboids through a computer search. The main result is the finding of 40 nets that fold into all three different cuboids with a surface area of 106. The secondary results are the finding of infinite families of nets that fold into three cuboid shapes, and the calculation of the number of common nets between smaller cuboids. The algorithms used to make the searches feasible will also be explained. The algorithms include taking advantage of some hidden structures in the nets that fold into the Nx1x1 cuboids, taking advantage of how a lot of nets fold into cuboid shapes in a 'striped' way, and using a variant of Redelmeier's algorithm. The paper ends with open questions that encourage the reader to broaden our collective understanding of the subject of creating polyomino nets.
The art gallery problem is a fundamental problem whose practical applications have inspired numerous variants. In this work, we investigate a setting in which full coverage of the gallery shall be ensured despite locational uncertainty of the guards. We study this problem for polyominoes under rectangular visibility, where a $k$-restless guard assigned to a cell may move to any cell within distance at most $k$. While all polyominoes are guardable for $k\in\{0, 1\}$, the same is not true for all $k\geq 2$. However, for a given polyomino $P$ and integer $k$, we present an algorithm that identifies a $k$-restless guard set of $P$ in polynomial time, or decides that no such set exists. For the cases $k\in\{0,1\}$, where $k$-restless guard sets always exist, we provide tight worst-case bounds on the number of $k$-restless guards that are always sufficient and sometimes necessary to guard a hole-free polyomino with $n$ vertices or $m$ cells. Moreover, we show that computing a minimum guard set is NP-hard. Complementing the hardness, we provide polynomial-time algorithms for solving the problem optimally for histograms, and leverage this to obtain a $20k$-approximation for polyominoes without holes.
An important question in counting complexity is whether exact counting can remain hard under restrictions that make feasibility easy. Tilings of squares by a fixed family of polyominoes provide a stringent test of this question, since tileability is polynomial-time decidable and the only varying input is a binary-encoded side length. We prove that there exists a fixed finite family of connected polyominoes for which counting translation-only square tilings is #EXP-complete under polynomial-time metric reductions, while the counting function belongs to #E. The resulting separation reveals that solution multiplicities can retain computational information that feasibility alone cannot capture. The proof develops a two-stage numerical isolation technique that combines a boundary-amplified Wang system with a rigid geometric compiler to recover accepting-computation counts while controlling all noncanonical tilings.
Exact-One Hitting Set is one of Karp's original 21 NP-complete problems: given an explicitly listed family of subsets of an $r$-element ground set, decide whether a subset meets every input set in exactly one element. Combining our reduction with the fixed-width exact-counting theorem of OpenAI (2026), we obtain a deterministic polynomial-space algorithm that computes the exact number of feasible selections in time $2^{O(r\log\log(r+16)/\sqrt{\log(r+16)})}\operatorname{poly}(L+1)=2^{o(r)}\operatorname{poly}(L+1)$, where $L$ is the input length. The number and widths of the input sets are unrestricted. Known row selection retains at most $r+1$ input constraints, but their total width may remain quadratic. Our path representation of two-query counting cancellation constructs two ordinary 3-CNF formulas with at most $2r$ variables and $O(r^2)$ clauses each, whose model counts differ by the desired answer. The auxiliary-variable budget depends on the number of simultaneous conditions, not on their widths or on the numbers of witnesses. We extend this construction to signed equations with fixed bounded demands and positive integer coefficients. We also represent every explicitly listed Boolean relation of VC dimension at most one by binary clauses and signed exact-one equations on its original variables, obtaining the same two-query variable bound for unrestricted overlaps among such local constraints. A bounded-term version further handles fixed finite/cofinite local degree rules on arbitrary graphs. The path representation is related by variable elimination to existing marker--parity cancellation.
We give randomized approximation algorithms for counting k-paths and k-forests in a host graph. Here k denotes the number of pattern vertices, n and m denote the numbers of host vertices and edges or arcs, ε is the relative error, and δ is the failure probability. Our main results are: 1. Paths: We approximate the number of directed paths on $k$ vertices in $2^k k^{O(1)}(n+m)\varepsilon^{-2}\log(2/δ)$ arithmetic operations. 2. Trees and forests: For every fixed $η>0$, we approximate the number of non-induced copies of a given forest on $k$ vertices in $(2+η)^k n^{O_η(1)}\varepsilon^{-2}\log(2/δ)$ arithmetic operations. Our path algorithm resolves a conjecture of Koutis and Williams~[CACM 2016] and answers an open question of Lokshtanov, Saurabh, and Zehavi~[SODA 2021] by giving a $2^k poly(n,\varepsilon^{-1})$-time approximation scheme. Our algorithms combine exterior algebra with random matrix estimators, using the tensor-train moment bound of Rakhshan and Rabusseau~[AISTATS 2020]. For forests, we use a small-component separator to evaluate the estimator efficiently.
The Pfaffian number of a graph is the minimum number of Pfaffians needed to obtain its perfect-matching polynomial by linear combination. In 2009, Norine conjectured that every Pfaffian number is a power of four. Miranda and Lucchesi disproved this conjecture in 2011 by constructing a graph of Pfaffian number six, and conjectured instead that every nontrivial Pfaffian number is even. We disprove their conjecture by proving that the Pfaffian number of $K_{3,3}\sqcup K_{3,3}$ is 13. We also construct a connected cubic bipartite matching-covered graph with Pfaffian number 13.
We study lattice-based collective construction of a target polyomino on the integer grid, where robots place unit square blocks subject to two physical constraints: the partial structure must remain connected at all times, and no placement may create an unfillable one-cell gap. We present a wavefront sweep algorithm that computes a dependency structure satisfying the local conditions required for safe assembly. Given a list of n cells sorted lexicographically by coordinates, the orientation can be computed in O(n) time using O(n) auxiliary space.