Algorithm and Hardness results on Liar's Dominating Set and $k$-tuple Dominating Set
Sandip Banerjee Sujoy Bhore



Department of Computer Science, Hebrew University of Jerusalem, Israel
sandip.ndp@gmail.com,Algorithms and Complexity Group, Technische Universität Wien, Austria  
sujoy@ac.tuwien.ac.at


Algorithm and Hardness results on Liar's Dominating Set and k-tuple Dominating Set
    Sandip Banerjee1,
Sujoy Bhore2
    
==================================================================================




plain
arabic






Given a graph G=(V,E), the dominating set problem asks for a minimum subset of vertices D⊆ V 
such that every vertex u∈ V∖ D is adjacent to at least one vertex v∈ D. 
That is, the set D satisfies the condition that |N[v]∩ D|≥ 1 for each v∈ V,
where N[v] is the closed neighborhood of v.
In this paper, we study two variants of the classical dominating set problem: k-tuple dominating set (k-DS) problem and 
Liar's dominating set (LDS) problem, and obtain several algorithmic and hardness results. 




On the algorithmic side, we present a constant factor (11/2)-approximation algorithm for the Liar's dominating set problem on unit disk graphs. 
Then, we obtain a PTAS for the k-tuple dominating set problem on unit disk graphs.
On the hardness side, we show a Ω (n^2) bits lower bound for the space complexity of any (randomized) streaming algorithm for Liar's dominating set problem as well as for the k-tuple dominating set problem. 
Furthermore, we prove that the Liar's dominating set problem on bipartite graphs is W[2]-hard.




§ INTRODUCTION

The dominating set problem is regarded as one of the fundamental problems in theoretical computer science
which finds its applications in various fields of science and engineering <cit.>.
A dominating set of a graph G=(V,E) is a subset D of V
such that every vertex in V∖ D is adjacent to at least one vertex in D.
The domination number, denoted as γ(G), is the minimum cardinality of a dominating set of G.
Garey and Johnson <cit.> showed that deciding whether a given graph has
domination number at most some given integer k is NP-complete.
For a vertex v∈ V, the open neighborhood of the vertex v denoted as N_G(v) is defined as N_G(v)={u|(u,v)∈ E}
and the closed neighborhood of the vertex v denoted as N_G[v] is
defined as N_G[v]=N_G(v)∪{v}.





  
k-tuple Dominating Set (k-DS): Fink and Jacobson <cit.> generalized
the concept of dominating sets as follows.


[colback=blue!3!white]
	 k-tuple Dominating Set (k-DS) Problem

	Input: A graph G=(V,E) and a non-negative integer k.

	Goal: Choose a minimum cardinality subset of vertices D⊆ V such that,
	for every vertex v∈ V, |N_G[v]∩ D|≥ k.



The k-tuple domination number γ_k(G) is the minimum cardinality of a k-DS of G.
A good survey on k-DS can be found in <cit.>.
Note that, 1-tuple dominating set is the usual dominating set, and 
2-tuple and 3-tuple dominating set are known as double dominating set <cit.>
and triple dominating set <cit.>, respectively. 
Further note that, for a graph G=(V,E), γ_k(G)=∞, if there exists no k-DS of G.
Klasing et al. <cit.> studied the k-DS problem from hardness and approximation point of view.
They gave a (log |V|+1)-approximation algorithm for the k-tuple domination problem in general graphs,
and showed that it cannot be approximated within a ratio of (1-ϵ)log |V|, for any ϵ>0.






  
Liar's Dominating Set (LDS):
Slater <cit.> introduced a variant of the dominating set problem called
Liar's dominating set problem. Given a graph G=(V,E), in this problem the objective is to
choose minimum number of vertices D⊆ V such that each vertex v∈ V is double dominated and
for every two vertices u,v∈ V there are at least three vertices in D from the union of their neighborhood set.
The LDS problem is an important theoretical model for the following real-world problem. 
Consider a large computer network where a virus (generated elsewhere in the Internet) can attack any of the processors in the network.

The network can be viewed as an unweighted graph. 
For each vertex v∈ G, an anti-virus can: (1) detect the virus at v as well as in its closed neighborhood N[v],
and (2) find and report the vertex u∈ N[v] at which the virus is located.
Notice that, one can make network G virus free by deploying the anti-virus at the vertices v∈ D,
where D is the minimum size dominating set.
However, in certain situations the anti-viruses may fail.
Hence to make the system virus free it is likely to double-guard the nodes of the network, which is indeed the 2-tuple DS.
But, if the anti-viruses detect the location of the viruses but fails to cure it properly 
due to some software error or corrupted circumstances. 
In this scenario, LDS serves the purpose. We define the problem formally below. 




[colback=blue!3!white]
	 Liar's Dominating Set (LDS) Problem

	Input: A graph G=(V,E) and a non-negative integer k.

	Goal: Choose a subset of vertices L⊆ V of minimum cardinality such that


  * for every vertex v∈ V, |N_G[v]∩ L|≥ 2,

  * for every pair of vertices u, v∈ V of distinct vertices |(N_G[u]∪ N_G[v])∩ L|≥ 3.







 §.§ Our Results

In this paper, we obtain seveal algorithmic and hardness results for LDS and k-DS problems on various graph families. 
On the algorithmic side in section <ref>, we present a constant factor (11/2)-approximation algorithm for the Liar's dominating set (LDS) problem on unit disk graphs. Then, we obtain a PTAS for the k-tuple dominating set (k-DS) problem on unit disk graphs. On the hardness side in section <ref>, we show a Ω (n^2) bits lower bound for the space complexity of any (randomized) streaming algorithm for Liar's dominating set problem as well as for the k-tuple dominating set problem. Furthermore, we prove that the Liar's dominating set problem on bipartite graphs is W[2]-hard.



§ ALGORITHMIC RESULTS




 §.§ Approximation Algorithm for LDS on Unit Disk Graphs

A unit disk graph (UDG) is an intersection graph  of a family of unit radius disks in the plane.
Formally, given a collection 𝒞={C_1,C_2,…,C_n} of n unit disks in the plane,
a UDG is defined as a graph G=(V,E), where each vertex u∈ V corresponds to a disk C_i∈𝒞
and there is an edge (u,v)∈ E between two vertices u and v if and only if their corresponding
disks C_u and C_v contain v and u, respectively. Here, we consider the geometric variant of LDS known as
Euclidean Liar's dominating set problem, which is defined as follows:




[colback=blue!3!white]
	 Liar's Dominating Set on UDG (LDS-UDG) Problem

	Input: A unit disk graph G=(𝒫, E), where 𝒫 is a set of n disk centers.

	Output: A minimum size subset D⊆𝒫 such that 
 
  
  * for each point p_i∈𝒫, |N[p_i]∩ D| ≥ 2.
  
  * for each pair of points p_i,p_j∈𝒫, |(N[p_i]∪ N[p_j])∩ D|≥ 3.
 


Jallu et al. <cit.> studied the LDS problem on unit disk graphs, and proved that this problem is NP-complete. Furthermore, given an unit disk graph G=(V,E)
and an ϵ>0, they have designed a (1+ϵ)-factor 
approximation algorithm to find an LDS in G with running time 
n^O(c^2), where c=O(1/ϵlog1/ϵ).
In this section, we design a 11/2-factor approximation algorithm that runs in sub-quadratic time.

For a point p∈𝒫, let C(p) denote the disk centered at the point p.
For any two points p,q∈𝒫, if q∈ C(p), 
then we say that q is a neighbor of p (sometimes we say q is covered by p) and vice versa.
Since for any Liar's dominating set D, |(N[p_i]∪ N[p_j])∩ D|≥ 3 (∀  p_i,p_j∈𝒫) holds,
we assume that |𝒫|≥ 3 and for all the points p∈𝒫, |N[p]|≥ 2.
For a point p_i∈𝒫, let p_i(x) and p_i(y) denote the x and y coordinates of p_i, respectively.
Let Cov_1/2(C(p_i)), Cov_1(C(p_i)) ,Cov_3/2(C(p_i)) ⊆ P denote the set of points
inside the circle centered at p_i and of radius 1/2, 1 and 3/2 unit, respectively.

The basic idea of our algorithm is as follows. 
Initially, we sort the points of 𝒫 based on their x-coordinates.
Now, consider the leftmost point (say p_i).
We compute the sets Cov_1/2(C(p_i)), Cov_1(C(p_i)) and Cov_3/2(C(p_i)).
Next, we compute the set Q=Cov_3/2(C(p_i))∖Cov_1/2(C(p_i)).
Further, for each point q_i∈ Q, we compute the set S(q_i)=Cov_1(C(q_i))∩Cov_1/2(C(p_i)).
Finally, we compute the set S=⋃ S(q_i).
Moreover, our algorithm is divided into two cases.





  
Case 1 (S∅):
For each point q_i∈ Q such that S(q_i)≠∅, we further distinguish between the following cases.



  * If |S(q_i)|≥ 3: we pick two arbitrary points from the set S(q_i), and include them in the output set D (see Figure <ref>(a)).


  * If |S(q_i)|≤ 2: in this case, we choose those two (or one) points (say p_a,p_b∈ S(q_i)) in the output set D 
(see Figure <ref>(b)).


Once these points are selected, we remove the remaining points from 
Cov_1(C(q_i)) at this step from the set Q.
Notice that the points that lie in Cov_1(C(q_i)) are already 1-dominated. 
Later, we can pick those points if required. 
However, observe that we may choose only 1 point from Cov_1/2(C(p_i)) while we are in the case of |S(q_i)|≤ 2.
So we maintain a counter t in Case 1. 



This counter keeps track of how many points we are picking from the set S(q_i) in total, for each point q_i∈ Q. 
If t is at least 2, we simply add p_i to the output set and do not enter into Case 2. 
Otherwise, we proceed to Case 2. 









  
Case 2 (S=∅ or t<2):
here, we further distinguish between the following cases.




  * If |Cov_1/2(C(p_i))|≥ 3: then we choose 2 points arbitrarily in the output set D (see Figure <ref>(a)).



  * If |Cov_1/2(C(p_i))| = 2: let p_i,p_x∈Cov_1/2(C(p_i)) be these points. 
We include both of them in the output set D.
This settles the first condition of LDS for them.
However, in order to  fulfill the second condition of LDS for p_i and p_x, we must include at least one extra point here. 
First, we check the cardinality of X=(Cov_1(C(p_i))∩Cov_1(C(p_x)))∖{p_i,p_x}.
If |X|≠∅, then we pick an arbitrary point p_m from X, and include p_m in D.
Otherwise, we include two points p_l∈Cov_1(C(p_i)) and p_r∈Cov_1(C(p_x)), and include them in D (see Figure <ref>(b)).
Note that, in this case, we know that p_l and p_r exist due to the input constraint of an LDS problem. 



  * If |Cov_1/2(C(p_i))|=1: then we check Cov_1(C(p_i)) and include two points
p_m and p_n arbitrarily from Cov_1(C(p_i))∖Cov_1/2(C(p_i)) (see Figure <ref>(c)).



This fulfills the criteria of LDS of points in Cov_1/2(C(p_i)).
Then we delete the remaining points of Cov_1/2(C(p_i)) from 𝒫. Next we select the left-most point from the remaining  and repeat the same procedure until 𝒫 is empty. The pseudocode is given in Algorithm <ref>.










algorithmProcedure





algorithmProcedure




The set D obtained from Algorithm <ref>, is a liar's dominating set of the unit disk graph defined on the points of 𝒫. 






Algorithm <ref> primarily relies on two cases.
We begin with the leftmost point (say p_i).
We first compute the sets Cov_1/2(C(p_i)), Cov_1(C(p_i)) and Cov_3/2(C(p_i)).
Then, we consider the points that lie in Q= (Cov_3/2(C(p_i))∖Cov_1/2(C(p_i))).
If the disks centered at these points of radius 1 share points with Cov_1/2(C(p_i)),
we choose points from their intersection to D.
This choice is based on the number of points available in the intersection. 
For every point p_k∈ Q,
if |S(p_k)|≥ 3 (S(p_k)=Cov_1(C(p_k))∩Cov_1/2(C(p_i))), we arbitrarily choose 2 points in D.
Otherwise, we choose one or two points in D, based on the cardinality of S(p_k).
Once these points are selected, we remove the remaining points of Cov_1(C(p_k)) at this step from the set Q.
Notice that the points lying in Cov_1(C(q_i)) are already 1-dominated. 
Later, we can pick those points if required.  
Clearly, after this process any point that lies in Cov_3/2(C(p_i)) and
shares points with Cov_1/2(C(p_i)) is at least 1-dominated or 2-dominated,
Notice that for any point that lies outside Cov_3/2(C(p_i)), its corresponding disk does not share any region with Cov_1/2(C(p_i)).
Later, for any points in Cov_3/2(C(p_i)) if we have to choose points from Cov_1/2(C(p_i)) to fulfill the 
criteria of LDS, we already took them in the output set at this stage. 
Meanwhile, we maintain a counter t that keeps track of how many points we are picking from Cov_1/2(C(p_i)), for each point p_k∈ Q. 
If t is at least 2, we know |Cov_1/2(C(p_i))∩ D| ≥ 2.
We simply add p_i to the output set and do not enter into Case 2.
Otherwise, we proceed to Case 2. 
Besides, if there is no point p_x∈ (Cov_3/2(C(p_i))∖Cov_1/2(C(p_i))),
such that the disk centered at p_x shares points with Cov_1/2(C(p_i)), we are in Case 2. 

Now we show the correctness of Case 2. 
In this case, if |Cov_1/2(C(p_i))|≥ 3, then we include three points arbitrarily including p_i (say p_i, p_j, p_k in D).
Note that, the distance between any two points p_l,p_r∈Cov_1/2(C(p_i)) is at most 1.
Since we are including 3 points from Cov_1/2(C(p_i)) in D, it fulfills the criteria 
of LDS of the points contained inside the unit disk centered at p_i.
Next, consider the case if |Cov_1/2(C(p_i))|=2. 
Let p_x be the other point in Cov_1/2(C(p_i)). 
We compute X=(Cov_1(C(p_i))∩Cov_1(C(p_x)))∖{p_i,p_x}.
Note that, due to the definitions of the problem, we know
|Cov_1(C(p_i))|≥ 3 and |Cov_1(C(p_x))|≥ 3.
When |X|≠∅ we include an additional point arbitrarily (say p_m∈ X)
in D to fulfill the second condition of the LDS of the points p_i, p_x ∈Cov_1/2(C(p_1)).
While |X|=∅, we include 2 points p_m and p_n
(both the points are chosen arbitrarily) from Cov_1(C(p_i)) and Cov_1(C(p_x)),
respectively. Notice that this makes the points p_i and p_x individually 2 dominated. 
Now, for any pair of points from Cov_1(C(p_i)), at least 3 points are chosen (that is, p_i,p_x,p_m). 
Finally, when |Cov_1/2(C(p_i))|=1, we include
two points p_m, p_n ∈Cov_1(C(p_i)) arbitrarily in D
to fulfill the criteria of LDS for p_i. 
Note that the existence of two points p_m and p_n in the set Cov_1(C(p_i)) follows from the problem constraint.

Thus, at every iteration, we made sure that the considered disk and the points inside that disk, fulfills the criteria of LDS.
Furthermore, due to Case 1, we have taken sufficient points from the considered disk for the disks that intersect with it. This completes the proof. 










 
Algorithm <ref> outputs a liar's dominating set D⊆𝒫 of the unit disk graph defined on the points of 𝒫 with approximation ratio 11/2.






For each point p_i∈𝒫, we consider the set Cov_1/2(C(p_i)) and choose points from this set.
Consider the disk C(p_i) of radius 3/2.
Notice that the points that lie outside the set Cov_3/2(C(p_i)), their corresponding disks of radius 1, do not share any points with the set
 Cov_1/2(C(p_i)).
Thus, we only need to consider the points inside Cov_3/2(C(p_i)).
The half-perimeter of the of the disk C(p_i) of radius 3/2 is (π·3/2) ≈ 4.71 
(since we are only considering the points which are to the right of p_i). 
Thus, we can pack at most 5 disks of radius 1 inside C(p_i) such that they mutually do not contain the center of other disks 
(see Figure <ref>).
We consider the points that lie in (Cov_3/2(C(p_i))∖Cov_1/2(C(p_i))).
If the disks centered at these points of radius 1 share points with Cov_1/2(C(p_i)),
we choose points from their intersection to D.
Now, for each point q_i∈ (Cov_3/2(C(p_i))∖Cov_1/2(C(p_i))), we choose at most two points 
from Cov_1/2(C(p_i)) ∩Cov_1(C(q_i)) (see Procedure <ref>). 
Once these points are selected, we remove the remaining points at this step from the set Q (recall that Q=(Cov_3/2(C(p_i))∖Cov_1/2(C(p_i)))).
The points that lie inside this disk, is already 1-dominated.
Later, we can pick the point itself, if required. 
Besides we also pick p_i. 
In this case, we pick at most (5× 2)+1 = 11.





Now, if there is no point in (Cov_3/2(C(p_i))∖Cov_1/2(C(p_i))), whose corresponding disk that shares a region Cov_1/2(C(p_i)),
or the number of points picked from Cov_1/2(C(p_i)) is less than 2, we enter into Case 2 (see Procedure <ref>).
Here, we include at most three points including the point p_i. However, we enter into this case only when sufficient points have not been picked in Case 1. 
Thus, in this case we have picked fewer than 11 points from Cov_1(C(p_i)) (precisely, we pick 4 points). 

Now, any optimal solution contains at least two points from Cov_1(C(p_i)), for each point p_i∈𝒫.
Since we have to fulfill the first constraint of the LDS that each disk is individually 2 dominated. 
Hence, we get the approximation factor 11/2. 







Algorithm <ref> clearly runs in polynomial time (to be precise in sub-quadratic time). Thus, from Lemma <ref> and Lemma <ref> we conclude the following theorem. 


Algorithm <ref> computes a liar's dominating set D⊆𝒫 of the unit disk graph defined on the points of 𝒫 in sub-quadratic time
with approximation ratio 11/2.






 §.§ PTAS for k-DS on Unit Disk Graphs

In this section we give a PTAS for the k-tuple dominating set on unit disk graphs with a similar approach used by Nieberg and Hurink <cit.>. It might be possible to design a PTAS by using local search or shifting strategy for the k-tuple dominating set problem on unit disk graphs. However, the complexity of these algorithms would be dependent on n and k. 
Thus we use the approach of Nieberg and Hurink <cit.>, that gurantees a better running time. 

Let G=(V,E) be an unit disk graph in the plane. 
For a vertex v∈ V, let N^r(v) and N^r[v]=N^r(v) ∪{v} be the
r-th neighborhood and r-th closed neighborhood of v, respectively.
For any two vertices u,v∈ V, let δ(u,v) be the distance
between u and v in G, that is the number of edges of a shortest path between u and v in G.
Let D_k(V) be the minimum k-tuple dominating set of G.
For a subset W⊆ V, let D_k(W) be the minimum k-tuple dominating set of
the induced subgraph on W.
We prove the following theorem. 


There exists a PTAS for the k-tuple dominating set problem on unit disk graphs.





The 2-separated collection of subsets is defined as follows:
Given a graph G=(V,E), let S={S_1,…,S_m} be a collection of
subsets of vertices S_i⊂ V, for i=1,…,m, such that
for any two vertices u∈ S_i and v∈ S_j with i j, δ(u,v)>2.
In the following lemma we prove that the sum of the cardinalities of the minimum 
k-tuple dominating sets D_k(S_i) 
for the subsets S_i∈ S of a 2-separated collection is 
a lower bound on the cardinality of D_k(V).


Given a graph G=(V,E), let S={S_1,…,S_m} be a 2-separated
collection of subsets then, |D_k(V)|≥∑_i=1^m |D_k(S_i)|.







Consider a subset S_i∈ S, and its neighborhood N[S_i].
We know from the properties of 2-separated collection of subsets that,
any two subsets S_i,S_j∈ S are disjoint for each i j.
Any vertex outside N[S_i] has at least distance more than one to any vertex in S_i.
Hence, D_k(V)∩ N[S_i] has to be a k-tuple domination of the vertices of S_i, where
D_k(V) is the k-tuple domination of G.
Otherwise the vertices of S_i is not k-tuple dominated,
since no vertex outside N[S_i] can dominate a vertex of S_i.
On the other hand, we know D_k(S_i)⊂ N[S_i].
This implies D_k(S_i) ≤ D_k(V)∩ N[S_i].
Hence, ∑_i=1^m |D_k(S_i)| ≤∑_i=1^m|D_k(V)∩ N[S_i]| ≤ |D_k(V)|. 





From Lemma <ref>, we get the lower bound of the minimum
k-tuple dominating set of G.
If we can enlarge each of the subset S_i to a subset T_i
such that the k-tuple dominating set of S_i (that is D_k(S_i))
is locally bounded to the k-tuple dominating set of T_i (that is D_k(T_i)),
then by taking the union of them we get an approximation of the k-tuple dominating set of G.
For each subset S_i, let there is a subset T_i (where S_i⊂ T_i),
and let there exists a bound (1+ϵ) (0<ϵ<1) such that
|D_k(T_i)|≤ (1+ϵ)· |D_k(S_i)|.
Then, if we take the union of the k-tuple dominating sets of all T_i,
this is a (1+ϵ)-approximation of the k-tuple dominating sets of the 
union of subsets S_i (for i=1,…,m).





Now, we describe the algorithm. 
We begin with an arbitrary vertex v∈ V, and compute
the k-tuple dominating sets of minimum cardinality for these neighborhoods until D_k(N^r+2[v]) > ρ· D_k(N^r[v]) 
(for a constant ρ).
Then, this process is used iteratively on the remaining graph induced by
V_i+1 = V_i∖ N^r̂_̂î+2[v_i] (where r̂_̂î is the first point at ith iteration when the condition is violated).
Let ℓ be the total number of iterations, where ℓ < n.
Let {N_1,…,N_ℓ} be the neighborhoods achieved from this process.
The following lemma shows that a k-tuple dominating set for the entire graph G
is given by the union of the sets D_k(N_i).


Let {N_1,…,N_ℓ} be the set of neighborhoods created by the above algorithm. 
The union ⋃^ℓ_i=1 (D_k(N_i)) forms a k-tuple 
dominating set of G.





Consider the set V_i+1=V_i∖ N_i, and we know N_i⊂ V_i. 
Thus, V_i+1=V_i ∪ N_i.
The algorithm stops while V_ℓ+1=∅, which means V_ℓ=N_ℓ.
Besides, ⋃^ℓ_i=1 (N_i)=V.
Thus, if we compute the k-tuple dominating set D_k(N_i) of each N_i, their union clearly is the 
k-tuple dominating set of the entire graph.
 





These subsets N^r̂_̂î[v_i], for i=1,…, ℓ, created by the algorithm
form a 2-separated collection {N^r̂_̂1̂[v_1],…, N^r̂_̂ℓ̂[v_ℓ]} in G.
Consider any two neighborhoods N_i,N_i+1.
We have computed N_i+1 on graph induced by V∖ N_i (where N_i = N^r̂_̂î+2[v_i]).
So, for any two vertices u∈ N_i and v∈ N_i+1, the distance is at least 2.
Thus we have the following corollary. 


The algorithm returns a k-tuple dominating set ⋃^ℓ_i=1 (D_k(N_i)) of cardinality no more
than (1+ϵ) the size of a dominating set D_k(V).



It needs to be shown that this algorithm has a polynomial running time.
The number of iterations ℓ is clearly bounded by |V|=n.
It is important to show that for each iteration
we can compute the minimum k-tuple dominating set D_k(N^r[v]) in polynomial time
for r being constant or polynomially bounded.

Consider the r-th neighborhood of a vertex v, N^r[v].
Let I^r be the maximal independent set of the graph induced by N^r[v].
From <cit.>, we have I^r≤ (2r+1)^2 = O(r^2).
The cardinality of a minimum dominating set in N^r[v]
is bounded from above by the cardinality of a maximal independent set in N^r[v].
Hence, |D(N^r[v]| ≤ (2r+1)^2 = O(r^2).
Now, we prove the following lemma. 




|D_k(N^r[v])| ≤ O(k^2· r^2).






For a vertex v∈ V, let N^r[v] be the r-th closed neighborhood of v.
Let I^r_1 be the first maximal independent set of N^r[v].
We know |D(N^r[v])| ≤ |I^r_1| ≤ (2r+1)^2.

Now, we take the next maximal independent set I^r_2 from N^r[v] ∖ I^r_1, and take the union of them (I^r_1 ∪ I^r_2).
Notice that every vertex v∈ (N^r[v] ∖ (I^r_1∪ I^r_2)) has 2 neighbors in (I^r_1∪ I^r_2),
so they can be 2-tuple dominated by choosing vertices from (I^r_1∪ I^r_2).  
Also, every vertex v∈ I^r_2 can be 2-tuple dominated by choosing vertices from (I^r_1∪ I^r_2), 
since v itself can be one and the other one can be picked from I^r_1. 
Additionally, for each vertex in u ∈ I^r_1, we take a vertex z from the neighborhood of u in (N^r[v] ∖ (I^r_1∪ I^r_2)).
Let W(I^r_1) be the union of these vertices. 
Now, every vertex v∈ N^r[v] can be 2-tuple dominated by choosing vertices from (I^r_1 ∪ I^r_2 ∪ W(I^r_1)). 
So, |D_2(N^r[v])| ≤ |(I^r_1 ∪ I^r_2 ∪ W(I^r_1))|.
|(I^r_1 ∪ I^r_2 ∪ W(I^r_1))| ≤ 3· (2r+1)^2. Hence, |D_2(N^r[v])| ≤ 3· (2r+1)^2.
We continue this process k times. 


After k steps, we get the union of the maximal independent sets  A={I^r_1 ∪…∪ I^r_k}.
Additionally, we get the unions of B={W(I^r_1) ∪ W(I^r_1∪ I^r_2) ∪…∪ W(I^r_1∪…∪ I^r_k-1)}.
Notice that every vertex v∈ N^r[v] can be k-tuple dominated by choosing vertices from (A∪ B).
The cardinality of (A∪ B) is at most (2r+1)^2 · (1+3+…+(2k-1)), which is (2r+1)^2 · k^2.
We also know |D_k(N^r[v])| is upper bounded by (A∪ B). 
Thus, |D_k(N^r[v])| ≤ (2r+1)^2 · k^2 ≤ O(k^2· r^2).
 



Nieberg and Hurink <cit.> showed that for a unit disk graph, there exists a bound on r̂_̂1̂
(the first value of r that violates the property D(N^r+2[v]) > ρ· D(N^r[v])).
This bound depends on the approximation ρ not on the size of the of the unit disk graph G=(V,E) given as input.
Precisely, they have proved that there exists a constant c = c(ρ) such that r̂_̂1̂≤ c,
that is, the largest neighborhood to be considered during the iteration of the algorithm is bounded by a constant.
Putting everything together, we conclude the proof.





§ HARDNESS RESULTS




 §.§ Streaming Lower Bound for LDS

In this section, we study the LDS problem in the streaming model. In the streaming model, the vertex set is fixed, and the edges appear one-by-one in sequential order. We are required to decide whether we remember this edge or forget at this particular time step. We show that in order to solve the LDS problem, one needs to essentially store the entire graph. We prove the following theorem by using similar approach used in <cit.>.


Any randomized (by randomized algorithm we mean that the algorithm should succeed
with probability ≥2/3) streaming algorithm for LDS problem on n-vertex graphs 
requires Ω(n^2) space.





We reduce from the Index problem in communication complexity. 
In the Index problem, Alice has a string X∈{0,1}^N given by
x_1… x_N and Bob has an index i∈ [N]. Now, Bob wants to find x_i, i.e., the i^th bit of X.
There is a lower bound of Ω(N) bits in the one-way randomized communication model for Bob to compute x_i (for any i∈ [N]) <cit.>.
Let us consider an instance of the Index problem where N is a perfect
square, and let r=√(N). Let us fix any bijection from [N]→ [r] × [r]. We interpret the bit string as an adjacency matrix of a
bipartite graph with r vertices on each side, where V, W are two 
partites. 

Now, we construct an instance G_X of the LDS. Assume that, Alice has an algorithm that solves the LDS problem by using f(r) bits.
Firstly, we insert the edges corresponding to the edge interpretation of
X between nodes v_i and w_j: for each i,j ∈ [k], 
Alice adds the edge (v_i, w_j) if the corresponding entry in X is 1, and sends the memory contents of her algorithm to Bob by using f(r) bits. Now, Bob has the index i ∈ [N] that he interprets as (I,J), under the same bijection ϕ:[N]→ [r] × [r].
He receives the memory contents of the algorithm, and does the following — (1) adds two vertices a and b, and an edge a-b,
(2) adds an edge from each vertex of V∖ v_I to a,
(3) adds an edge from each vertex of W∖ w_J to a,
(4) adds five vertices {u,y,u',y',z} and edges u-u', y-y', u-z and y-z, (5) adds an edge from each vertex of V∪ W∪{a,b} to each vertex from {u,y}.



Let D be a minimum LDS of G_X. Notice that, firstly, D needs to be a 2-tuple DS of G_X. 
Since u' has only 2 neighbors in G_X, it follows that {u,u'}⊆ D. 
Similarly, {y,y'}⊆ D. 
Note, z also has only two neighbors in G_X.
Therefore, N[z]∪ N[b] = {u,y,a,b}. 
Since we should have |(N[z]∪ N[b])∩ D| ≥ 3,
at least one of a/b must be in D. 
Since N[b]⊆ N[a], w.l.o.g., we can assume that a∈ D. 
Therefore, we conclude that {u,u',y,y',a}⊆ D.


Next, we show that finding the minimum value of a LDS of G_X
allows us to solve the corresponding instance X of Index.



x_i = 1 implies that the minimum size of a liar's dominating set of G_X is 6.





 Suppose that x_i = 1, i.e., v_I-w_J is an edge in G_X. We now claim that D:={u,u',y,y',a}∪ v_I is a LDS of G_X.

First, we check that D is a 2-tuple DS of G_X;

  
  * For each vertex in λ∈ G_X∖{u,u',y,y',z} we have (N[λ]∩ D)⊇{u,y}
  
  * (N[u]∩ D)⊇{u,u'}
  
  * (N[y]∩ D)⊇{y,y'}
  
  * (N[z]∩ D)= {u,y}
  
  * (N[u']∩ D)= {u,u'}
    
  * (N[y']∩ D)= {y,y'}


Now we check the second condition. 
Let T=G_X∖{u,u',y,y',z}, and T' = G_X∖ T


  * For each λ∈ T∖{v_I, w_J} and each δ∈ T' we have (N[λ]∪ N[δ])∩ D ⊇{a,u,y}

  * For each δ∈ T' we have (N[v_I]∪ N[δ])∩ D ⊇{v_I,u,y}

  * For each δ∈ T' we have (N[w_J]∪ N[δ])∩ D ⊇{v_I,u,y}

  * Now we consider pairs where both vertices are from T'. By symmetry, we only have to consider following choices
        
        
  * (N[u']∪ N[u])∩ D = {u,u',y}
        
  * (N[u']∪ N[z])∩ D = {u,u',y}
        
  * (N[u']∪ N[y])∩ D = {u,u',y,y'}
        
  * (N[u']∪ N[y'])∩ D = {u,u',y,y'}
        

  * Now we consider pairs where both vertices are from T. By symmetry, we only have to consider following choices
        
        
  * For each λ∈ V∖ v_I ∪ W∖ w_J we have (N[λ]∪ N[b])∩ D ⊇{u,y,a} and  (N[λ]∪ N[a])∩ D ⊇{u,y,a}
        
  * (N[v_I]∪ N[b])∩ D ⊇{u,y,a}
        
  * (N[v_I]∪ N[a])∩ D ⊇{u,y,a}
        
  * (N[w_J]∪ N[b])∩ D ⊇{u,y,a}
        
  * (N[w_J]∪ N[a])∩ D ⊇{u,y,a}
        
  * (N[w_J]∪ N[v_I])∩ D ⊇{v_I,y,a}
        
  * For each γ∈ V∖ v_I we have (N[w_J]∪ N[γ])∩ D ⊇{v_I,y,a,u}
        
  * For each γ∈ W∖ w_J we have (N[v_I]∪ N[γ])∩ D ⊇{v_I,y,a,u}
        
  * For each γ∈ V∖ v_I and γ'∈ W∖ w_J we have (N[γ]∪ N[γ'])∩ D ⊇{y,a,u}
        

Hence, it follows that D is indeed a LDS of G_X of size 6.
 


x_i = 0 implies that the minimum size of a LDS of G_X is ≥ 7.



 Now suppose that x_i = 0, i.e., v_I and w_J do not have an edge between them in G_X.
Let D' be a minimum LDS of G_X. We have already seen above that {u,u',y,y',a}⊆ D.
Consider the pair (v_I, z). Currently, we have that (N[v_I]∪ N[z])∩{u,u',y,y',a} = {u,y}.
Hence, D' must contain a vertex, say μ∈ N[v_I]∖{u,y}. Consider the pair (w_J, z).
Currently, we have that (N[w_J]∪ N[z])∩{u,u',y,y',a} = {u,y}.
Hence, D' must contain a vertex, say μ'∈ N[w_J]∖{u,y}.
Since v_I and w_J do not form an edge, we have that μ≠μ'. Hence, |D'|≥  7.
 


Thus, by checking whether the value of a minimum LDS on the instance
G_X is 6 or 7, Bob can determine the index
x_i.

The total communication between Alice and Bob was O(f(r)) bits,
and hence we can solve the Index problem in f(r) bits. Recall that the
lower bound for the Index problem is Ω(N)=Ω(r^2).
Note that |G_X|=n=2r+5=O(r), and hence Ω(r^2)=Ω(n^2).



Let ϵ>0 be a constant. Any (randomized) streaming algorithm
that achieves a (7/6-ϵ)-approximation for a liar's dominating set requires Ω(n^2) space.



Theorem <ref>
shows that distinguishing between whether the minimum value of
the LDS is 6 or 7 requires Ω(n^2) bits. The claim follows since 6· (7/6-ϵ) <7









 §.§ Streaming Lower Bounds for k-DS



For any k=O(1), any randomized (by randomized algorithm we mean that the algorithm
should succeed with probability ≥2/3) streaming algorithm
for the k-tuple dominating set problem on n-vertex graphs requires Ω(n^2) space.















We reduce from the Index problem. We construct an instance G_X
of k-tuple dominating set.
Assume that Alice has an algorithm that solves the k-tuple dominating set problem using f(r) bits.


First, we insert the edges corresponding to the edge interpretation of
X between nodes v_i and w_j:
  for each i, j ∈ [k], Alice adds the edge (v_i, w_j) if
  the corresponding entry in X is 1.
Then, Alice sends the memory contents of her algorithm to Bob, using
f(r) bits.

Now, Bob has the index i ∈ [N], which he interprets as (I,J) under
the same bijection ϕ:[N]→ [r] × [r].
Bob receives the memory contents of the algorithm, and does the following — (1) adds (k+1) vertices A={a_1, a_2, …, a_k} and b,
(2) adds edges {a_i-b : 1≤ i≤ k},
(3) adds an edge from each vertex of V∖ (v_I) to each vertex of A, (4) adds an edge from each vertex of V∖ (w_J) to each vertex of A, (5) adds an edge v_I to each vertex of A∖ a_k,
(6) adds an edge from w_J to each vertex of A∖ a_k.










Now we show finding the minimum value of a k-tuple dominating set of G_X
allows us to solve the corresponding instance X of Index.



The minimum size of a k-tuple dominating set of G_X is k+1 if and only if
x_i = 1.







Let D be a minimum k-DS of G_X. Since b has only k neighbors in G_X, we can assume, w.l.o.g., A⊆ D. Observe, every vertex in G_X∖{v_I , w_J} already has k neighbors in A. Both v_I and w_J have exactly k-1 neighbors in A. Hence, |D|≥ k+1.

Suppose that

x_i = 1, i.e., v_I-w_J is an edge in G_X. We now claim that A∪ v_I is a k-tuple dominating set of G_X.
We have observed above that each vertex in G_X∖ has k neighbors in A⊆ D.
So we just need to verify the condition for v_I and w_J now.
The claim follows since N[v_I]∩ D = {a_1, a_2, …, a_k-1}∪ v_I = N[w_J]∩ D, and |{a_1, a_2, …, a_k-1}∪ v_I|=k.

Now suppose that x_i = 0, i.e., v_I and w_J do not have an edge between them in G_X. Note that A∪ v_I ∪ w_J is indeed a k-tuple dominating set for G_X of size k+2. We now claim that G_X has no k-tuple dominating set of size k+1. Suppose to the contrary that there is a k-tuple dominating set D' of G_X of size k+1. Since A has to be part of any minimum k-tuple dominating set, it follows that D'=A∪β for some vertex β∈ G_X ∖ A. We now consider all choices for where the vertex β can be chosen from (and derive a contradiction in each case):

  
  * β=b: Then we have |N[v_I]∩ D'|=k-1
  
  * β∈ V: Then we have |N[v_I]∩ D'|=k-1
  
  * β∈ W: Then we have |N[w_J]∩ D'|=k-1

This completes the proof. 
 


Thus, by checking whether the value of minimum k-tuple dominating set on the instance
G_X is k+1 or k+2, Bob can determine the index
x_i.

The total communication between Alice and Bob was O(f(r)) bits,
and hence we can solve the Index problem in f(r) bits. Recall that the
lower bound for the Index problem is Ω(N)=Ω(r^2). Note that |G_X|=n=2r+k+1=O(r) since k=O(1), and hence Ω(r^2)=Ω(n^2).



Let 1>ϵ>0 be any constant. Any (randomized) streaming algorithm that approximates a k-tuple dominating set within a relative error of
ϵ requires Ω(n^2) space.



Choose ϵ=1/k. Theorem <ref>
shows that the relative error is at most 1/k+2, which is less than ϵ.
Hence finding an approximation within ϵ relative error amounts to
finding the exact value of the k-tuple dominating set. Hence, the claim follows from the lower bound of Ω(n^2)
of Theorem <ref>.





 §.§ W-Hardness Results for LDS

The LDS problem was shown to be NP-complete on general graphs by Slater in <cit.>,
where the problem was introduced.
Later this problem was considered in <cit.>, and was shown to be
NP-complete on bipartite graphs, split graphs and planar graphs.
In <cit.>, Bishnu et al. proved that the LDS problem on planar graphs admits
a linear kernel, and is W[2]-hard while considered on general graphs.
We study the LDS problem on bipartite graphs and show that it is 
W[2]-hard. 
Our approach is inspired by the W[2]-hardness results of <cit.>.


Liar's dominating set on bipartite graphs is W[2]-hard.




We prove this by giving a parameterized reduction from the dominating set problem in general undirected graphs.
Let (G=(V,E), k) be an instance of the dominating set, where k denotes the size of the dominating set.
We construct a bipartite graph G'=(V', E') from G=(V,E).
First, we create two copies of V, namely V_1={u_1|u∈ V} and V_2={u_2|u∈ V}.
Next, we introduce two extra vertices z_1,z_2 in V_1, and two extra vertices z_1',z_2' in V_2.
Furthermore, we introduce two special vertices s_z'_1, s_z'_2 in V_1 and two special vertices s_z_1, s_z_2 in V_2.
The entire vertex set V' is V_1∪ V_2, where V_1={u_1|u∈ V}∪{z_1,z_2, s_z'_1, s_z'_2} and 
V_2={u_2|u∈ V}∪{z_1',z_2', s_z_1, s_z_2}.
Now, if there is an edge (u,v)∈ E, then we draw the edges (u_1,v_2) and (v_1,u_2).
We draw the edges of the form (u_1,u_2) in G' for every vertex u∈ V.
Then, we add edges from every vertex in V_1∖{z_1,z_2, s_z'_1, s_z'_2} to z_1',z_2',
and the edges from every vertex in V_1∖{z'_1,z'_2, s_z_1, s_z_2} to z_1,z_2.
Finally we add the edges (z_1,z'_1), (z_2,z'_2) and (z_1, s_z_1), (z_2, s_z_2), (z'_1, s_z_1), (z'_2, s_z'_2).
This completes the construction (see Figure <ref>).


	



We show that G has a dominating set of size k if and only if G' has a LDS of size k+8.
Let D denote the dominating set of the given graph G.
We claim that D'={u_1|u∈ D}∪{z_1,z_2, s_z'_1, s_z'_2}∪{z_1',z_2', s_z_1, s_z_2} 
is a LDS of G'.
Note that for any vertex v∈ V', |N_G'[v]∩ D'|≥ 2, since 
{z_1,z_2,z_1',z_2'} is in D'.
This fulfills the first condition of the LDS.
Now, for every pair of vertices, u,v∈ V', we show that |(N_G'[u]∪ N_G'[v])∩ D'|≥ 3.
If u,v∈ V_1, we know |(N_G'[u]∪ N_G'[v])∩ D'|≥ 2 due to z'_1,z'_2.
Now, in the dominating set at least one additional vertex dominates them. 
Thus, |(N_G'[u]∪ N_G'[v])∩ D'|≥ 3.
Similarly, when u,v∈ V_2 or u∈ V_1 and v∈ V_2.
This fulfills the second condition of the LDS. 



Conversely, let D' be a LDS in G'.
Note that, {z_1,z_2,z'_1,z'_2} are always part of D', since z_1,z_2 are the only neighbors of s_z_1, s_z_2 and
z'_1,z'_2 are the only neighbors of s_z'_1, s_z'_2.
These special vertices are taken in the construction to enforce {z_1,z_2,z'_1,z'_2} to be in D'.
Now we know, for any pair of vertices p,q, |(N_G'[p]∪ N_G'[q])∩ D'|≥ 3.
This implies p,q is dominated by at least one vertex or one of them is picked,
except {z_1,z_2,z'_1,z'_2}.
Otherwise, |(N_G'[p]∪ N_G'[q])∩ D'|< 3.
This violates the second condition of LDS.
Now, when p,q are both part of the same edge in G (say u_2,v_2 ∈ V_2 ; see Figure <ref>), 
we need at least one vertex from {u_1,v_1,u_2,v_2} in D'.
This means that for every vertex v∈ V, |N_G[v]∩ D|≥ 1.
Thus, D is a dominating set of G where the cardinality of D is at most k.





 §.§ Acknowledgements

The authors would like to thank Rajesh Chitnis and M. S. Ramanujan 
for interesting discussions during various stages of the research.

abbrv

