Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949495 | Discrete Applied Mathematics | 2017 | 11 Pages |
Abstract
A set DâV is called a k-tuple dominating set of a graph G=(V,E) if |NG[v]â©D|â¥k for all vâV, where NG[v] denotes the closed neighborhood of v. A set DâV is called a liar's dominating set of a graph G=(V,E) if (i) |NG[v]â©D|â¥2 for all vâV and (ii) for every pair of distinct vertices u,vâV, |(NG[u]âªNG[v])â©D|â¥3. Given a graph G, the decision versions of k-Tuple Domination Problem and the Liar's Domination Problem are to check whether there exist a k-tuple dominating set and a liar's dominating set of G of a given cardinality, respectively. These two problems are known to be NP-complete (Liao and Chang, 2003; Slater, 2009). In this paper, we study the parameterized complexity of these problems. We show that the k-Tuple Domination Problem and the Liar's Domination Problem are W[2]-hard for general graphs. It can be verified that both the problems have a finite integer index and satisfy certain coverability property. Hence they admit linear kernel as per the meta-theorem in Bodlaender (2009), but the meta-theorem says nothing about the constant. In this paper, we present a direct proof of the existence of linear kernel with small constants for both the problems.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Arijit Bishnu, Arijit Ghosh, Subhabrata Paul,