Complexity of chess domination problems
Open Access
- 8 February 2025
- journal article
- research article
- Published by Springer Nature in Research in the Mathematical Sciences
- Vol. 12 (1) , 1-26
Abstract
We study different domination problems of attacking and non-attacking rooks and queens on polyominoes and polycubes of all dimensions. Our main result proves that maximum independent domination is NP-complete for non-attacking queens and for non-attacking rooks on polycubes of dimension three and higher. We also analyze these problems for polyominoes and convex polyominoes, conjecture the complexity classes, and provide a computer tool for investigation. We have also computed new values for classical queen domination problems on chessboards (square polyominoes). For our computations, we have translated the problem into an integer linear programming instance. Finally, using this computational implementation and the game engine Godot, we have developed a video game of minimum domination of queens and rooks on randomly generated polyominoes.Keywords
All Related Versions
Funding Information
- Fonds de Recherche du Quebec- Nature et Technologies (270527)
- HORIZON EUROPE Marie Sklodowska-Curie Actions (754462)
- Fonds Wetenschappelijk Onderzoek (EOS3088945)
- Bundesministerium für Forschung, Technologie und Raumfahrt (ScaDS.AI)
- Max Planck Institute for Mathematics in the Sciences
This publication has 20 references indexed in Scilit:
- Art Gallery Problem with Rook and Queen VisionGraphs and Combinatorics, 2021
- Domination in Chessboards2020
- Core-Boosted Linear Search for Incomplete MaxSAT2019
- Chasing First Queens by Integer Programming2018
- Parallelizing the dual revised simplex methodMathematical Programming Computation, 2017
- Computational Complexity of the $r$-visibility Guard Set Problem for Polyominoes2014
- Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph DrawingsLecture Notes in Computer Science, 2013
- The Art Gallery Theorem for PolyominoesDiscrete & Computational Geometry, 2012
- A unified approach to visibility representations of planar graphsDiscrete & Computational Geometry, 1986
- Towards a theory of domination in graphsNetworks, 1977