Indian Science Technology and Engineering facilities Map
Supplier Map
Service Map


Publication Details

Indian Institute of Technology (IIT) Patna 
S. Paul, Arijit Bishnu, Arijit Ghosh 
Corresponding Authors:
Subhabrata Paul 
DOI #: 
Linear kernels for k-tuple and liar’s domination in bounded genus graphs 
Discrete Applied Mathematics 
k-tuple domination, Liar’s domination, Planar graphs, Bounded genus graphs, Kernelization W[2]-hard 
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. 
Entered by:
Venkata Dantham on 2020-08-04 
I-Mitra(आई-मित्र) Welcomes You..
It has always been the basic tenet of the Government of India, in generously funding R&D efforts at academic institutions over the years, that facilities established through such support be made available to those needing them and qualified to make use of them for their own research work

However, this was never easy or straightforward for, among other reasons, there was no ready source of information of what facility was available and where. Thanks to the Web, it is much easier today to have a national and regional “inventory of resources”, so as to match users with the resources they need, and to do all this in an efficient and transparent manner.

This can lead to a leap in R&D productivity and greatly enhance the effectiveness of public investment. This is the motivation behind I-STEM.
read less <<
Visitor Hit Counter
Hosted at Indian Institute of Science
Copyright © 2020 I-STEM. All rights reserved.
Audited by: STQC Bengaluru.