Structural Parameterization of Minus Domination
摘要
Given a graph \(G = (V, E)\) , a minus dominating function \(f: V \rightarrow \{-1, 0 ,1\}\) is a labelling of vertices such that \(\sum _{v \in N[u]} f(v) \ge 1\) , for each \(u \in V\) . The weight of f is the sum of f(u) over all the vertices \(u \in V\) . The objective of Minus Dominating Set problem is to compute a minus dominating function of minimum weight. The problem is known to be NP-complete even on split graphs and bipartite graphs. The parameterized complexity of the problem for the parameter treewidth is a long standing open question. In this paper, we answer this by proving that the problem is W[1]-hard for the parameter distance to disjoint paths, which is larger than treewidth and feedback vertex set number. Later, we show that no polynomial kernel exists for the parameter vertex cover number. For the parameter weight, we prove that the problem is W[2]-hard on bipartite graphs and W[1]-hard on circle graphs, respectively. In addition, we provide an FPT algorithm for the parameter feedback edge set number.