NP-completeness of maximal non-attacking queen domination on convex polyominoes

A polyomino is a finite union of edge-connected unit squares in the plane. It is convex if every row and every column has at most one connected component. A set of queens is non-attacking when no two queens attack each other, and the maximal domination problem asks whether such a set dominates the polyomino.

Convex-polyomino maximal queen domination conjecture. The maximal domination problem for non-attacking queens on convex polyominoes is NP-complete.

The corresponding maximal non-attacking rook problem is known to be in P, but the queen problem has not been settled. The paper notes that existing gadgets are non-convex and leaves this conjecture open.