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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Structural Parameterization of Minus Domination

  • Sangam Balchandar Reddy,
  • Anjeneya Swami Kare

摘要

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.