2026/07/21 by Toranosuke Kokai, Rin Saito, Tatsuhiro Suga +2
Computer Science · #cs.DS
In the Odd Domination problem, given a graph G and a positive integer k, the task is to determine whether there exists a vertex subset D of G such that the closed neighborhood of each vertex in G contains an odd number of vertices from D. In this paper, we investigate the computational complexity of the problem. When parameterized by the solution size k, we establish W[1]-hardness on some restricted graphs and a sharp boundary between fixed-parameter tractability and W[1]-hardness with respect to the girth of the input graph. Then, we address the problem when parameterized by several structural graph parameters. Furthermore, we investigate the parameterized complexity of Parity Domination, which is a generalization of Odd Domination.