2013/09/21 by Arijit Bishnu, Arijit Ghosh, Bishnu, Arijit +3
Computer Science · #05C69 #05C85 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #acm:05C69 #acm:05C85 #cs.CC #cs.DS #msc:05C69 #msc:05C85
paper · pdf · doi:10.48550/arxiv.1309.5461
Title changed from "Parameterized complexity of k-tuple and liar's domination" to "Linear kernels for k-tuple and liar's domination in bounded genus graphs"
openalex publication_date 2013/09/21 · arxiv created 2014/08/18 · arxiv updated 2014/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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 exists 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 \citeLiaoChang2003, Slater2009. 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 but they admit linear kernels for graphs with bounded genus.