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 splitgraphs, and (4) unless P = NP there is no fixed-parameter algorithm for minus-domination. ? Springer International Publishing 2013.
Relation:
7th International Conference on Combinatorial Optimization and Applications, COCOA 2013 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),V.8287 LNCS,P.178-189
