NP-completeness of minimal rook domination on convex polyominoes

A polyomino is a finite union of edge-connected unit squares in the plane. It is row-convex if each row has at most one connected component, column-convex if each column has at most one connected component, and convex if it is both row-convex and column-convex. The minimal domination problem asks for the smallest attacking or non-attacking rook set that dominates the polyomino.

Convex-polyomino rook domination conjecture. The minimal domination problem for attacking or non-attacking rooks on convex polyominoes is NP-complete.

Minimal rook domination is trivial on square polyominoes but NP-complete on general polyominoes. The cited result of Alpert implies that proving the attacking-rook case is equivalent to proving the non-attacking case; the conjecture remains open.