On $d$-distance $m$-tuple ($\ell, r$)-domination in graphs
Sangram K. Jena Ramesh K. Jallu Gautam K. Das
cs.CC cs.DM math.CO


Exploiting the Redundancy in Convolutional Filters for Parameter Reduction 

    [
     ^⋆  Laboratoire d'Informatique et des Systèmes, Université de Toulon, Aix Marseille Univ, CNRS UMR 7020, LIS, Marseille, France

boizot@univ-tln.fr; 

^†  Department of Mathematics, Lehigh University, Bethlehem, PA, USA. 

lus219@lehigh.edu; 

 

This research has been partially supported by the ANR SRGI (reference ANR-15-CE40-0018). 


This is a post-peer-review, pre-copyedit version of an article published in Journal of Mathematical Imaging and Vision (JIMIV). The final authenticated version is available online at: <http://dx.doi.org/10.1007/s10851-020-00990-5>

   
      
   

 
 

====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================







In this article, we study the d-distance m-tuple (ℓ, r)-domination problem. Given a simple undirected graph G=(V, E), 
and positive integers d, m, ℓ and r, a subset V' ⊆ V is said to be a d-distance m-tuple (ℓ, r)-dominating 
set if it satisfies the following conditions: (i) each vertex v ∈ V is d-distance dominated by at least m vertices in V', and 
(ii) each r size subset U of V is d-distance dominated by at least ℓ vertices in V'. Here, a vertex v is d-distance 
dominated by another vertex u means the shortest path distance between u and v is at most d in G. A set U is d-distance dominated by a set of ℓ vertices means size of the union of the d-distance neighborhood of all vertices of U in V' is at least ℓ. 
The objective of the d-distance m-tuple (ℓ, r)-domination problem is to find a minimum size subset V' ⊆ V 
satisfying the above two conditions.

We prove that the problem of deciding whether a graph G has (i) a 1-distance m-tuple (ℓ, r)-dominating set for each fixed value of m, ℓ, and r, and (ii) a d-distance m-tuple  (ℓ, 2)-dominating set for each fixed value of d (> 1), m, and ℓ of cardinality at most k (here k is a positive integer) are NP-complete. We also prove that for any ε>0, the 1-distance m-tuple (ℓ, r)-domination problem and the d-distance m-tuple (ℓ,2)-domination problem cannot be approximated within a factor of (1/2- ε)ln |V| and (1/4- ε)ln |V|, respectively, unless P = NP.





§ INTRODUCTION



Given a simple undirected graph G=(V,E), δ_G(v_i,v_j) denotes the length of a shortest path between the 
vertices v_i and v_j in G. For an integer d >0, the d-distance neighborhood of a vertex v_i ∈ V is denoted by 
N_G^d[v_i] and is defined as  N_G^d[v_i] = {v_j∈ V |δ_G(v_i,v_j) ≤ d}. 
A d-distance m-tuple (ℓ,r)-dominating set ((d, m, ℓ, r) set for short) of G is a subset V'⊆ V such that (i) for every v_i ∈ V, |N^d_G[v_i]∩ V'| ≥ m, and (ii) |(∪_u ∈ U N^d_G[u]) ∩ V'| ≥ℓ for every r size subset U of V, where d, m, r, and ℓ are positive integers. 
If m ≥ℓ, then the second condition in the definition of (d, m, ℓ, r) set is redundant. In the case of 
m = ℓ (=k, say), the (d, m, ℓ, r) set is known as k-tuple dominating set in the literature. Note that, if m = ℓ then the value of r>1 is irrelevant. Therefore, we assume r=1 in case of m=ℓ. From now onwards, 
we assume that m ≤ℓ. If d=1, m = 2, ℓ = 3, r=2 then (d, m, ℓ, r) set is known as a liar's dominating 
set in the literature. The objective of the d-distance m-tuple (ℓ, r)-domination problem is to find a minimum size  d-distance m-tuple (ℓ, r) dominating set in a given graph G, and we call this problem as the minimum (d, m, ℓ, r) dominating set  problem. In Figure <ref>, the set of vertices {e,f,i} form a 3-distance 2-tuple (3, 4)-dominating set for the graph.




Our interest in the problem arises from its important application such as fault tolerance in wireless/sensor networks. One specific real-time application is as follows for r=2. 
Suppose that in a graph G=(V,E) each vertex is a possible location for an intruder such as a thief, a saboteur, a fire or some possible fault. Assume also that there is exactly min (ℓ-m, ℓ/2-1) intruders in the system represented by G. A protection device placed at a vertex v is assumed to be able to (i) detect the intruder at any vertex in its d-distance neighborhood N^d_G[v], and (ii) report the vertex u ∈ N^d_G[v] at which the intruder is located. 
We are interested in deploying protection devices at a minimum number of 
vertices so that the intruder can be detected and identified correctly. 
This can be solved by finding a minimum cardinality m-tuple dominating set, say D, of G and deploying protection devices at all the vertices of D. 
If any one protection device can fail to detect the intruder, then to correctly detect and identify the intruder one needs to place the protection devices at all the vertices of a minimum cardinality 2m-tuple dominating set of G. Now it may so happen that all the protection devices detect the intruder location correctly but while reporting some of these protection devices can misreport or lie (either deliberately or through a transmission error) about the intruder location.
Assume that at most min (ℓ-m, ℓ/2-1) protection devices in the d-distance neighborhood of an intruder location can lie. 
Under these circumstances, to protect the network we have to install the protection devices at all the vertices of a minimum  d-distance m-tuple (ℓ, r) dominating set.





§ RELATED WORK



The domination problem is one of the most studied problem in the literature for its wide range of applications. Finding a minimum dominating set (MDS) in general graphs is  known to be NP-hard <cit.>. Raz and Safra <cit.> proved that there does not exist any approximation algorithm better than O(log n)-factor unless P=NP.  The concepts of dominations and its variations are widely studied and can be seen in <cit.>.

One of  the  variations  of  domination is the k-tuple domination problem and was introduced by Harary and Haynes <cit.>. When k=1, it is the usual domination problem.  For k=2, it is called double domination <cit.>. 
The same paper discusses exact values of  the  double domination numbers for  some  special graphs and various bounds  of  the  double  and  the k-tuple  domination numbers  in  terms  of  other  parameters. 
The hardness results and bounds for the k-tuple domination number for various sub-classes of graphs can be found in <cit.>. 

In 2009, Slater <cit.> first introduced 1-distance 2-tuple (3,2) domination problem known as the liar's dominating set (LDS) problem in the literature. The author proved that the problem is NP-hard for general graphs and proposed various bounds for trees, a subclass of trees, and graphs. The problem is also studied for different sub-classes of graphs and proved to be NP-hard  for  bipartite graphs  <cit.>, split graphs and chordal graphs <cit.>, doubly chordal graphs <cit.>,  whereas polynomially solvable in trees  <cit.>, block graphs <cit.>, proper interval graphs <cit.>.  
Panda et al. <cit.> studied the approximability of the problem and gave an O(lnΔ)-factor approximation algorithm, where Δ is the degree of the given graph. 

Alimadadi et al. <cit.> provided the characterization of graphs and trees for which the LDS cardinality is |V| and |V|-1, respectively. 





 §.§ Our contribution
 
We prove that the problem of deciding whether a graph G has a 1-distance m-tuple (ℓ, r)-dominating set for each fixed value of m, ℓ, and r of cardinality at most k is NP-complete (see Subsection <ref>).
Next, we prove that the problem of deciding whether a graph G has a d-distance m-tuple  (ℓ, 2)-dominating set for each fixed value of d (> 1), m, and ℓ of cardinality at most k is NP-complete (see Subsection <ref>).
We also prove that for any ε>0, the 1-distance m-tuple (ℓ, r)-domination problem and the d-distance m-tuple (ℓ,2)-domination problem cannot be approximated within a factor of (1/2- ε)ln |V| and (1/4- ε)ln |V|, respectively, unless P = NP (see Section <ref>).


§ HARDNESS RESULTS
 


 §.§ Hardness of the 1-distance m-tuple (ℓ, r)-domination problem

In this section, we show that the decision version of the 1-distance m-tuple (ℓ, r)-domination problem in graphs is NP-complete by reducing the dominating set (DS) problem to it, which is known to be NP-complete <cit.>.

The definition of the decision version of both the problems are as follows:


  Decision version of 1-distance m-tuple (ℓ, r)-domination problem: 

  Instance: A simple undirected graph G = (V,E) with at least ℓ vertices and three positive integers m, r, and k (≤ |V|), where m ≤ℓ.


  Question: Does G has a 1-distance m-tuple (ℓ, r)-dominating set of size at most k?

 


  Decision version of the DS problem:


  Instance: A simple undirected graph G=(V,E)  and a positive integer k.



  Question: Does there exist a dominating set D of G such that |D| ≤ k?



 The decision version of the  problem is NP-complete.



 For any given set L⊆ V and a positive integer k, we can verify whether L is a 1-distance m-tuple 
(ℓ, r)-dominating set of size at most k or not in polynomial time by checking both the conditions of 
1-distance m-tuple (ℓ, r)-dominating set. Therefore, 1-distance m-tuple (ℓ, r)-domination problem is in NP.

Now, we prove the hardness of the 1-distance m-tuple (ℓ, r)-domination problem by reducing the decision version of the DS problem, which is known to be NP-complete <cit.>, to it.
Let <G=(V,E),k> be an instance of the dominating set problem, where G=(V,E) is an undirected graph with vertex set V={v_1,v_2, … ,v_n} and k is an integer. 
We construct an instance <G'=(V',E'),m,ℓ, r> of the decision version of 1-distance m-tuple (ℓ, r)-domination problem as follows: 

.5



    V'   =V^1∪ V^2∪ V^3, where
    
    V^1   ={v_1^1,v_2^1, … ,v_n^1},
    
    V^2   ={v_1^2,v_2^2, … v_ℓ-1^2},
    
    V^3   ={v_1^3,v_2^3, …, v_r^3}




.5



    E'   =E^1∪ E^2∪ E^3∪ E^4, where
    
     E^1   ={(v_i^1,v_j^1)| (v_i,v_j) ∈ E},
    
     E^2   ={(v_i^2,v_j^2)| 1≤ i<j≤ℓ-1},
    
     E^3   ={(v_i^1,v_j^2)| 1≤ i ≤ n, 1≤ j≤ℓ-1},
    
     E^4   ={(v_i^2,v_j^3)| 1≤ i ≤ℓ-1, 1 ≤ j ≤ r}





Observe that, G'=(V',E') can be constructed in polynomial time and |V'|=n+ℓ+r-1, where n=|V| and ℓ, r <n. 
An illustration for the construction of G' from G is shown in Figure <ref>(a).



Claim 1: G has a dominating set of size at most k if and only if G' has a 1-distance m-tuple (ℓ, r)-dominating set of size at most k+ℓ.

Proof: Let D be a dominating set of G and |D|≤ k. 
Let L={v_i^1 | v_i∈ D}∪ V^2∪{v_1^3}. 
Now, we show that L is a 1-distance m-tuple (ℓ, r)-dominating set in G'.

(i) Observe that for each v ∈ V', |N^1_G'[v] ∩ L| ≥ m as m ≤ℓ (value of r=1 in case of m = ℓ) 
and each v ∈ V' is dominated by ℓ-1 vertices in V^2.

(ii) Let U = {u_1, u_2, …, u_r}⊆ V' be an arbitrary subset of size r. 

Case 1: Let U ∩ V^2 ≠∅ and v_i^2 ∈ U ∩ V^2. From the construction of G', 
N_G^1[v_i^2] ∩ L ⊇ V^2 ∪{v_1^3}, which implies |N_G^1[v_i^2] ∩ L| ≥ℓ. Therefore, 
|(∪_u ∈ U N_G^1[u]) ∩ L| ≥ℓ. 

Case 2:  Let U ∩ V^1 ≠∅ and v_i^1 ∈ U ∩ V^1. From the constructions of G' and L, 
N_G^1[v_i^1] ∩ L ⊇ V^2 ∪{v_j^1}, where v_j ∈ D is a dominator of v_i in G. Therefore, |N_G^1[v_i^1] ∩ L| ≥ℓ, which leads to |(∪_u ∈ U N_G^1[u]) ∩ L| ≥ℓ. 

Case 3: Let U = V^3. Again, from the constructions of G and L, (∪_u ∈ U N_G^1[u]) ∩ L ⊇ V^2 ∪{v_1^3}. Therefore, 
in this case also |(∪_u ∈ U N_G^1[u]) ∩ L| ≥ℓ. 

Thus L is a 1-distance m-tuple (ℓ,r)-dominating set in G' and  |L| ≤ k+ℓ.

Conversely, let L be a 1-distance m-tuple (ℓ,r)-dominating set for G' of size at most k+ℓ. 
From the definition of the 1-distance m-tuple (ℓ,r)-dominating set and as |V^3| = r,  
|(∪_v ∈ V^3 N^1_G'[v] ) ∩ L|≥ℓ. 
Therefore, there must be at least ℓ vertices from V^2 ∪ V^3 in L (see Figure <ref>(a)). 
Let D={v_i∈ V| v_i^1∈ L ∖ (V^2 ∪ V^3)}. 
If D is a dominating set of G, then we are done as |D| ≤ k. 
Suppose D is not a dominating set in G. 
Since |V^2| is ℓ-1, the 1-distance neighborhood of every subset of V^1 with cardinality greater than or equal to r will have a non-empty intersection with D (due to the second condition of 1-distance m-tuple (ℓ,r)-domination). This implies, for any subset U^1 of V, D ∩ (∪_u ∈ U^1N^1_G[u])=∅ if and only if |U^1|≤ r-1. Note that such a set U^1 (≠∅) exists 
based on our assumption that D is not a dominating set of G. Let |U^1|=s. Now, we will show that |(V^2 ∪ V^3) ∩ L| ≥ℓ+s. 

Let U^2 (⊆ V^2) and U^3 (⊆ V^3) be the maximum size subsets such that U^2 ∩ L = ∅ and 
 U^3 ∩ L = ∅, respectively. Let s' = |U^2| and s” = |U^3|. Let U_13 = U^1 ∪ U^3. Since 
(∪_u ∈ U_13N^1_G'[u])∩ L = V^2∖ U^2, i.e., |(∪_u ∈ U_13N^1_G'[u])∩ L| = ℓ-1-s' < ℓ, 
|U_13| = s+s” < r. Add r-s-s” vertices from V^3∖ U^3 to the vertex set U_13. Now, by the definition of L 
the size of the set |(∪_u ∈ U_13N_G'^1[u])∩ L| must be at least ℓ. Therefore, r-s-s” + ℓ-1-s' ≥ℓ, 
which implies r-s”≥ s+s'+1.

Since r-s”≥ s+s'+1, |D|≤ k-s. Let D_1 = D ∪ U^1. So, every vertex in V is dominated by at least one vertex in D_1 whose size is at most k. Therefore, we conclude, the decision version of 1-distance m-tuple (ℓ,r)-domination problem is NP-complete. 




 §.§ Hardness of the d-distance m-tuple (ℓ,2)-domination problem

In this section, we show that the decision version of d-distance m-tuple (ℓ,2)-domination problem is NP-complete.
 For fixed constant d ≥ 2, the decision version of the problem is defined as follows.



  Instance: An undirected connected graph G = (V,E) with |V|≥ℓ and three positive integers m, d, and k (≤ |V|), where m ≤ℓ.



  Question: Does G has a d-distance m-tuple (ℓ,2)-dominating set of size at most k?


We prove that decision version of d-distance m-tuple (ℓ,2)-domination problem (d ≥ 2) is NP-complete by reducing the decision 
version of the 1-distance m-tuple (ℓ,2)-domination problem to it in polynomial time. Note that 1-distance m-tuple 
(ℓ,2)-domination problem is NP-complete (see Section <ref>). Recall, the decision version of 1-distance m-tuple (ℓ,2)-domination problem: 


 
  Instance: An undirected connected graph G = (V,E) with |V|≥ℓ and two positive integer m, k ≤ |V|, where m ≤ℓ.


 
  Question: Does G has a 1-distance m-tuple (ℓ,2)-dominating set of size at most k?



The decision version of the d-distance m-tuple (ℓ,2)-domination problem is NP-complete.



The decision version of the d-distance m-tuple (ℓ,2)-domination problem is in NP as for a given certificate (a subset of V) we can verify whether it is satisfying both the conditions of the d-distance m-tuple (ℓ,2)-dominating set or not in polynomial time.

We now describe a polynomial time reduction from an arbitrary instance 
of the decision version of 1-distance m-tuple (ℓ,2)-domination problem to an instance of the 
decision version of the d-distance m-tuple (ℓ,2)-domination problem.

Let G=(V={v_1,v_2, … ,v_n},E) be an arbitrary instance of the decision version of 1-distance m-tuple 
(ℓ,2)-domination problem. We construct an instance, a graph G'=(V',E'), of the decision version of the 
d-distance m-tuple (ℓ,2)-domination problem as follows:



    V'   ={v_i'| v_i ∈ V}∪ (⋃_v_i ∈ V{v_i1',v_i2',…,v_id-1'})   (see Figure <ref>(b) for an example)
    
    E'   ={(v_i',v_j') | (v_i,v_j)∈ E}∪ 
    (⋃_v_i ∈ V{(v_i',v_i1'),(v_i1',v_i2'),…,(v_id-2',v_id-1')})



Claim 2: G has a 1-distance m-tuple (ℓ,2)-dominating set of cardinality at most k if and only if 
G' has a d-distance m-tuple (ℓ,2)-dominating set of cardinality at most k.

Necessity: Let L be a 1-distance m-tuple (ℓ,2)-dominating set of G such that |L|≤ k. 
Let L'={v_i' ∈ V' | v_i ∈ L}. We can argue that L' is a d-distance m-tuple (ℓ,2)-dominating set in G' and |L'| ≤ k.
Since |L'| = |L| and |L|≤ k, so |L'| ≤ k. As each vertex v ∈ V satisfies 
1-distance m-tuple (ℓ,2)-domination properties and each vertex in G' is at most d-1 distance 
away from a vertex in L', L' suffices to ensure d-distance m-tuple (ℓ,2)-dominating set in graph G' for d ≥ 2.

Sufficiency: Let L' be a d-distance m-tuple (ℓ,2)-dominating set in G' such that |L'|≤ k. We shall show that, 
by updating (i.e., removing or replacing) some of the vertices in L', at most k vertices from 
{v_1',v_2',…,v_n'} can be chosen such that the set of corresponding vertices in V is an  
1-distance m-tuple (ℓ,2)-dominating set in G. Let L”=L'. For each vertex v_ij' ∈ V', 
(1 ≤ j ≤ d-1 and 1 ≤ i ≤ n) we do the following: if v_ij' ∈ L”, then replace it with its 
associated vertex v_i' if v_i' is not already in L”, otherwise, replace it with any vertex in 
N^1_G'[v_i'] ∩{v_1',v_2',…,v_n'} which is not in L”. If all the vertices of 
N^1_G'[v_i'] ∩{v_1',v_2',…,v_n'} are in L” 
(i.e., (N^1_G'[v_i']∩{v_1',v_2',…,v_n'}) ⊆ L” ), then remove v_ij' from L”. 
Therefore, |L”| ≤ k. Let L={v_i ∈ V | v_i' ∈ L”}. Now, we prove that L is an 
1-distance m-tuple (ℓ,2)-dominating set in G such that |L|≤ k. 

Since |L”|≤ k, then |L| ≤ k. We first prove the first condition (i.e., for every v ∈ V, 
|N^1_G[v]∩ L| ≥ m) of 1-distance m-tuple (ℓ,2)-dominating set. Consider a vertex  v_i' ∈ V', for some 
1 ≤ i ≤ n, let s be the number of vertices in L' ∩{v_i1',v_i2',…,v_id-1'}.

Case 1. s=0.  
Since L' is d-distance m-tuple (ℓ,2)-dominating set, there must exist at least m vertices, say {v_1”,v_2”, …, v_m”} in {v_1',v_2', …,v_n'}∩ L' such that {v_1”,v_2”, … , v_m”}⊆ N^d_G'[v_i,d-1'], otherwise, L' is not a feasible solution as v_id-1' does not have m distance-d (m,ℓ)-dominators. 
Therefore, |N^1_G'[v_i'] ∩ ({v_1',v_2', …,v_n'}∩ L”)|≥ m.

Case 2. s ≥ 1. 
Let v_ij_1',v_ij_2', …, v_ij_t'∈ L', for some 1≤ j_1,j_2, …, j_t≤ d-1. 
By our construction of L” each vertex in {v_ij_1',v_ij_2', …, v_ij_t'} is replaced by one of the vertices in N^1_G'[v_i'] ∩{v_1',v_2', …,v_n'}. 
Therefore, in this case also |N^1_G'[v_i'] ∩ ({v_1',v_2', …,v_n'}∩ L”)| ≥ m. Thus, by our construction of L from L”, |N^1_G[v_i] ∩ L|≥ m is true.

Now we prove the second condition of 1-distance m-tuple (ℓ,2)-dominating set (i.e., for every pair of distinct vertices u,v ∈ V, |(N^1_G[u]∪ N^1_G[v])∩ L| ≥ℓ).

Let v_i and v_j be two distinct vertices in G. Consider the vertices v_id-1' and v_jd-1' in G'.  
As L' is a d-distance m-tuple (ℓ,2)-dominating set of G', it satisfies the second property of d-distance m-tuple (ℓ,2)-domination in G'. 
Thus there exist at least ℓ dominators dominating v_id-1' and v_jd-1' in L', i.e., |(N^d_G'[v_id-1']∪ N^d_G'[v_jd-1'])∩ L'|≥ℓ.
These dominators are either from N^1_G[v_i'] ∪ N^1_G[v_j'] or from 
{v_i1',v_i2',…,v_id-1'} and/or from {v_j1',v_j2' …,v_jd-1'}.
As per our construction of L” from L', we are replacing each dominator in {v_i1',v_i2',…,v_id-1'}∪{v_j1',v_j2' …,v_jd-1'} (if any) by a vertex in (N^1_G'[v_i'] ∪ N^1_G'[v_j']) ∩{v_1',v_2',…,v_n'}.

Since G is connected and |V|≥ℓ, so is G'. Therefore, L” contains  at least ℓ vertices from (N^1_G'[v_i'] ∪ N^1_G'[v_j']) ∩{v_1',v_2',…,v_n'}, i.e., |(N^1_G'[v_i'] ∪ N^1_G'[v_j']) ∩{v_1',v_2',…,v_n'}∩ L”| ≥ℓ. 
Therefore, according to the construction of L from L”, |(N^1_G[v_i] ∪ N^1_G[v_j]) ∩ L| ≥ℓ. 
Thus, L is a 1-distance m-tuple (ℓ,2)-dominating set of the graph G having cardinality at most k.

 Therefore, the decision version of d-distance m-tuple (ℓ,2)-domination problem is NP-complete.





§ INAPPROXIMABILITY RESULTS




 §.§ Inapproximability of the 1-distance m-tuple (ℓ,r)-domination problem
 
In this section, we prove that the 1-distance m-tuple (ℓ,r)-domination problem cannot be approximated 
within a factor of (1/2- ε) ln(|V|) for any ε >0, unless P = NP.
We argue the claim by showing that if 1-distance m-tuple (ℓ,r)-domination problem can be approximated within a factor of (1/2- ε) ln(|V|) for any ε >0 in a graph G', then the domination problem can be approximated within a factor of (1- ε) ln(|V|) for any ε >0. 

 <cit.> 
For every ε >0, it is NP-hard to approximate set cover problem within a factor of (1- ε) ln n, where n is the size of the instance. The reduction runs in n^O(1/ε) time. 


 
Minimum domination problem cannot be approximated within a factor of (1- ε) ln(|V|) for any ε >0, unless P = NP.



The result follows from (i) the relation between set cover problem and dominating set problem, (ii) Theorem 
<ref>, and (iii) the inapproximability result in <cit.>.



Minimum 1-distance m-tuple (ℓ,r)-domination problem cannot be approximated within a factor of 
(1/2- ε) ln(|V|) for any ε >0, unless P = NP.



Let G be a simple graph.
Consider the construction of the graph G' for any given graph G as discussed in Section <ref>.
As per our construction, we proved that each instance of domination problem can be 
reducible to an instance of 1-distance m-tuple (ℓ,r)-domination problem in polynomial-time . 

Let D^* and L^* be the optimal DS and 1-distance m-tuple (ℓ,r)-dominating set in G and G', 
with cardinalities γ_ds(G)  and γ_m ℓ r(G'), respectively. Now we can argue the following 
claim: γ_m ℓ r(G')=γ_ds(G)+ℓ. The inequality γ_m ℓ r(G')≤γ_ds(G)+ℓ 
is trivial as per our construction in Section <ref>. On the other hand, 
γ_m ℓ r(G')≥γ_ds(G)+ℓ follows from the sufficiency proof of Claim 1 in Section <ref>. 
So given a dominating set D of G, one can find a 1-distance m-tuple (ℓ,r)-dominating set L of G' such that 
|L|=|D|+ℓ. Now, |L|/|L^*|=|D|+ℓ/|D^*|+ℓ≥1/2|D|/|D^*|. Suppose 
there exists a polynomial time algorithm that approximates 1-distance m-tuple (ℓ,r)-domination problem within 
a factor of (1/2- ε) ln N for graphs with N vertices. As per our construction of the graph G' from 
G (see Figure <ref>(a)), G' contains, N=n+ℓ+r - 1 ≤ 3n for  n ≥ 2 vertices, where n is the 
total number of vertices in G, ℓ < n, and r < n. Therefore,



    |D|/|D^*|≤  (1- 2ε) ln N ≤ (1- 2ε) ln n(1+ ln 4/ln n).



For sufficiently large n, the term (1+ ln 4/ln n) can be bounded by 1+ε/5, 
where ε≥5 ln 4/ln n. Now we have



    (1- 2ε) ln n(1+ ln 4/ln n) ≤ (1- 2ε)[ln n + ln (1+ ε/5)] ≤ 
    (1- 2ε)[ln n +  ε/5ln n] ≤ (1- ε')ln n,



where ε' < 9/5ε+ 2/5ε^2. Therefore, for an arbitrary graph, we can 
approximate the domination problem by a factor of (1-ε')ln n, which leads to a contradiction to 
Theorem <ref>. Thus, the minimum 1-distance m-tuple (ℓ,r)-domination problem cannot 
be approximated within a factor of (1/2- ε) ln(|V|) for any ε >0, unless P = NP.




 §.§ Inapproximability of the d-distance m-tuple (ℓ,2)-domination problem


In this section, we give a lower bound on the approximation ratio of any approximation algorithm for the 
d-distance m-tuple (ℓ,2)-domination problem by providing an approximation preserving reduction from the 
1-distance m-tuple (ℓ,r)-domination problem for r=2.


Given a simple undirected graph G=(V,E), the d-distance m-tuple (ℓ,2)-domination problem cannot be approximated within a 
factor of (1/4- ε)ln |V|, for any fixed constant d≥ 2 and ε>0, unless P = NP.



Let G=(V,E) be an arbitrary instance of the 1-distance m-tuple (ℓ,2)-domination problem with n vertices.
Given G=(V,E), we construct a graph G'=(V',E'), an instance of the d-distance m-tuple (ℓ,2)-domination problem as described in Section <ref>. Let L^* and L_d^* be the optimal 1-distance m-tuple (ℓ,2)-dominating set and 
d-distance m-tuple (ℓ,2)-dominating set in G and G', with cardinalities γ_m ℓ(G)  and γ_m ℓ^d(G'), respectively.
Now we can argue the following claim: γ_m ℓ^d(G')=γ_m ℓ(G).
The inequality γ_m ℓ^d(G')≤γ_m ℓ(G) is trivial as every 1-distance m-tuple (ℓ,2)-dominating set 
of G is a d-distance m-tuple (ℓ,2)-dominating set in G'. On the other hand, γ_m ℓ^d(G')=|L_d^*|≥ |L| follows from the 
sufficiency proof of Claim 2 in Section <ref>. 

Given any 1-distance m-tuple (ℓ,2)-dominating set L of G, one can find a d-distance m-tuple (ℓ,2)-dominating set L_d 
of G' with |L_d|=|L|. Suppose there exist a polynomial time algorithm to approximate d-distance m-tuple (ℓ,2)-domination problem 
within a factor of (1/4-ε)ln |V'|, where |V'| = n + n(d-1) ≤ n^2 (see Section <ref>).
Now |L|/|L^*|=|L_d|/|L_d^*|≤ (1/4-ε)ln n^2 = (1/2-2ε)ln n≤ (1/2-ε')ln n, where ε' ≤ 2ε. 
Therefore, the result follows from Theorem <ref>.


 

§ CONCLUSION

In this article, we studied d-distance m-tuple (ℓ, r)-domination problem. We provided a common NP-completeness 
proof of the 1-distance m-tuple (ℓ, r) domination problem for each fixed value of m, ℓ, and 
r. We also presented a common NP-completeness proof of the d-distance m-tuple  (ℓ, 2) domination 
problem for each fixed value of d (> 1), m, and ℓ. We have showed that the first problem is not approximated 
within a factor of (1/2- ε)ln |V| for each fixed value of m, ℓ, and r, unless P = NP 
and the second problem is not approximated within a factor of (1/4- ε)ln |V| for each fixed value of  d (> 1), m, and ℓ, unless P = NP, where V is the vertex set of the input graph. The reduction in the NP-completeness/inapproximability proofs are very powerful as these are common reductions for completely different kind of dominations. 





plain
10


alimadadi
A. Alimadadi, M. Chellali, and D. A. Mojdeh.
Liar's dominating sets in graphs.
Discrete Applied Mathematics, 211:204–210, 2016.

chleb
M. Chlebík and J. Chlebíková.
Approximation hardness of dominating set problems in bounded degree
  graphs.
Information and Computation, 206(11):1264–1275, 2008.

dinur
Irit Dinur and David Steurer.
Analytical approach to parallel repetition.
In Proceedings of the forty-sixth annual ACM symposium on Theory
  of computing, pages 624–633, 2014.

garey2002
R. M. Garey and D. S. Johnson.
Computers and intractability: A guide to the theory of NP-completeness.
W. H. Freeman and company, 1978.

harary
F. Harary and T. W. Haynes.
Double  domination  in  graphs.
Ars Combin., 55(2000) 201–213.

haynes208
T. W. Haynes, S. T. Hedetniemi and P. J. Slater.
Fundamentals of domination in graphs, Vol. 208,
Marcel Dekker Inc., New York 1998.

haynes209
T. W. Haynes, S. T. Hedetniemi and P. J. Slater.
Domination in Graphs: Advanced Topics, Vol. 209,
Marcel Dekker Inc., New York 1998.

liao2003k
C. S. Liao and G. J. Chang.
k-Tuple domination in graphs.
Information Processing Letters, 87(1):45–50, 2003.




















panda2013liar
B. S. Panda and S. Paul.
Liar's domination in graphs: Complexity and algorithm.
Discrete Applied Mathematics, 161(7):1085–1092, 2013.

paul2013
B. S. Panda and S. Paul.
A linear time algorithm for liar's domination problem in proper
  interval graphs.
Information Processing Letters, 113(19):815–822, 2013.







panda2015hardness
B. S. Panda, S. Paul, and D. Pradhan.
Hardness results, approximation and exact algorithms for liar's
  domination problem in graphs.
Theoretical Computer Science, 573:26–42, 2015.

raz1997sub
R. Raz and S. Safra.
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP.
STOC, 97:475–484,1997.

roden
M. L. Roden and P. J. Slater.
Liar's domination in graphs.
Discrete Mathematics, 309(19):5884–5890, 2009.

rautenbach2007new
D. Rautenbach and L. Volkmann.
New bounds on the k-domination number and the k-tuple domination number.
Applied mathematics letters, 20(1):98–102, 2007.

slater
P. J. Slater.
Liar's domination.
Networks, 54(2):70–74, 2009.







