On complexities of minus domination

A function f:V→{−1,0,1} is a minus-domination function of a graph G=(V,E) if the values over the vertices in each closed neighborhood sum to a positive number. The weight of f is the sum of f(x) over all vertices x∈V. In the minus-domination problem, one tries to minimize the weight of a minus-domination function. In this paper, we show that (1) the minus-domination problem is fixed-parameter tractable for d-degenerate graphs when parameterized by the size of the minus-dominating set and by d, where the size of a minus domination is the number of vertices that are assigned 1, (2) the minus-domination problem is polynomial for graphs of bounded rankwidth and for strongly chordal graphs, (3) it is NP-complete for split graphs, and (4) there is no fixed-parameter algorithm for minus-domination.