Algorithmic study on liar's vertex-edge domination problem

Let $G=(V,E)$ be a graph. For an edge $e=xy\in E$, the closed neighbourhood of $e$, denoted by $N_G[e]$ or $N_G[xy]$, is the set $N_G[x]\cup N_G[y]$. A vertex set $L\subseteq V$ is liar’s vertex-edge dominating set of a graph $G=(V,E)$ if for every $e_i\in E$, $\mathrm{\mid }{N}_G[e_i]\cap L\mathrm{\mid }\ge 2$ and for every pair of distinct edges $e_i$ and $e_j$, $\mathrm{\mid }(N_G[e_i]\cup N_G[e_j])\cap L\mathrm{\mid }\ge 3$. This paper introduces the notion of liar’s vertex-edge domination which arises naturally from some applications in communication networks. Given a graph $G$, the $\text{textsc}MinimumLia{r}^{\mathrm{\prime }}sVertex-EdgeDominationProblem$ ($\text{textsc}MinLVEDP$) asks to find a liar’s vertex-edge dominating set of $G$ of minimum cardinality. In this paper, we study this problem from algorithmic point of view. We show that $\text{textsc}MinLVEDP$ can be solved in linear time for trees, whereas the decision version of this problem is NP-complete for chordal graphs, bipartite graphs, and $p$-claw free graphs for $p\ge 4$. We further study approximation algorithms for this problem. We propose two approximation algorithms for $\text{textsc}MinLVEDP$ in general graphs and $p$-claw free graphs. %We propose an $O(\ln \mathrm{\Delta }(G))$-approximation algorithm for $\text{textsc}MinLVEDP$ in general graphs, where $\mathrm{\Delta }(G)$ is the maximum degree of the input graph. Also, we design a constant factor approximation algorithm for $p$-claw free graphs. On the negative side, we show that the $\text{textsc}MinLVEDP$ cannot be approximated within $\frac{1}{2}(\frac{1}{8}-\epsilon )\ln \mathrm{\mid }V\mathrm{\mid }$ for any $\epsilon >0$, unless $NP\subseteq DTIME(\mathrm{\mid }V{\mathrm{\mid }}^{O(\log (\log \mathrm{\mid }V\mathrm{\mid })})$. Finally, we prove that the $\text{textsc}MinLVEDP$ is APX-complete for bounded degree graphs and $p$-claw free graphs for $p\ge 6$.