Hardness of Liar's Domination on Unit Disk Graphs

Abstract

A unit disk graph is the intersection graph of a set of unit diameter disks in the plane. In this paper we consider liar's domination problem on unit disk graphs, a variant of dominating set problem. We call this problem as {\it Euclidean liar's domination problem}. In the Euclidean liar's domination problem, a set $\mathcal{P}=\{p_1,p_2,\dots ,p_n\}$ of $n$ points (disk centers) are given in the Euclidean plane. For $p\in \mathcal{P}$, $N[p]$ is a subset of $\mathcal{P}$ such that for any $q\in N[p]$, the Euclidean distance between $p$ and $q$ is less than or equal to 1, i.e., the corresponding unit diameter disks intersect. The objective of the Euclidean liar's domination problem is to find a subset $D(\subseteq \mathcal{P})$ of minimum size having the following properties : (i) $|N[p_i]\cap D|\ge 2$ for $1\le i\le n$, and (ii) $|(N[p_i]\cup N[p_j])\cap D|\ge 3$ for $i\ne j,1\le i,j\le n$. This article aims to prove the Euclidean liar's domination problem is NP-complete.

6 pages, 4 figures