Complexity of chess domination problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916660995162112 |
|---|---|
| author | Langlois-Rémillard, Alexis Müßig, Mia Róldan, Érika |
| author_facet | Langlois-Rémillard, Alexis Müßig, Mia Róldan, Érika |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_05651 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Complexity of chess domination problems Langlois-Rémillard, Alexis Müßig, Mia Róldan, Érika Combinatorics Computational Complexity Computational Geometry Discrete Mathematics 03D15, 05B40, 05B50, 00A08, 68Q17, 68R05, 68R07 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. |
| title | Complexity of chess domination problems |
| topic | Combinatorics Computational Complexity Computational Geometry Discrete Mathematics 03D15, 05B40, 05B50, 00A08, 68Q17, 68R05, 68R07 |
| url | https://arxiv.org/abs/2211.05651 |