{"id":"arxiv/2607.24668","url":"https://arxiv.org/abs/2607.24668","tags":["cs.CC","math.CO"],"score":0,"title":"Maximum independent queen set on polyominoes is NP-complete","domain":"cs.CC","source":"arxiv","authors":["Alexis Langlois-Rémillard","Mia Müßig"],"reviews":0,"subject":"cs.CC","summary":"Finding a set of vertices in a graph with no edges between them, INDSET, is a well-known NP-complete problem. The queen graph of a chessboard is constructed by taking vertices as the tiles of the chessboard and drawing edges between two tiles if a queen can move from one to the other. We call INDQUEENS the independent set problem on a queen graph where the chessboard is a polyomino. We prove that INDQUEENS on polyominoes is NP-complete, proving a conjecture of Langlois-Rémillard--Müßig--Roldán. As our reduction is parsimonious, we can further prove that it is #P-complete. We furthermore…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-27","reactions":{}}