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 N P -complete for split graphs, and (4) there is no fixed-parameter algorithm for minus-domination.