  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$, $|N_G[e_i]\cap L|\geq 2$ and for every pair
of distinct edges $e_i$ and $e_j$, $|(N_G[e_i]\cup N_G[e_j])\cap L|\geq 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 \textsc{Minimum Liar's Vertex-Edge Domination Problem} (\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 \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\geq 4$. We further study approximation
algorithms for this problem. We propose two approximation algorithms for
\textsc{MinLVEDP} in general graphs and $p$-claw free graphs.
  %We propose an $O(\ln \Delta(G))$-approximation algorithm for
\textsc{MinLVEDP} in general graphs, where $\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 \textsc{MinLVEDP} cannot be
approximated within $\frac{1}{2}(\frac{1}{8}-\epsilon)\ln|V|$ for any $\epsilon
>0$, unless $NP\subseteq DTIME(|V|^{O(\log(\log|V|)})$. Finally, we prove that
the \textsc{MinLVEDP} is APX-complete for bounded degree graphs and $p$-claw
free graphs for $p\geq 6$.
