Complexity of chess domination problems

作     者：Langlois-Remillard, Alexis Muessig, Mia Roldan, Erika 

作者机构：Univ Ghent Fac Sci Dept Appl Math Comp Sci & Stat Ghent Belgium Univ Leipzig ScaDS AI Leipzig Leipzig Germany Hausdorff Ctr Math Bonn Germany Ludwig Maximilian Univ Munchen Munich Germany Max Planck Inst Math Sci Inselstr 22 Leipzig Germany 

出 版 物：《RESEARCH IN THE MATHEMATICAL SCIENCES》 (Res. Math. Sci.)

年 卷 期：2025年第12卷第1期

页      面：1-26页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Fonds de recherche du Qubec- Nature et technologies 

主　　题：Art gallery theorem NP-completion NP-hardness Polyomino Computational geometry Visibility coverage Guard number Domination problem N-queens problem Linear programming 

摘      要：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.