  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$. In
this paper, we introduce the notion of liar's vertex-edge domination which
arise naturally from some application in communication network. Given a graph
$G$, the \textsc{Minimum Liar's Vertex-Edge Domination Problem}
(\textsc{MinLVEDP}) asks to find a minimum liar's vertex-edge dominating set of
$G$ of minimum cardinality. We have studied 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 general graphs.
We further study approximation algorithms for this problem. 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.
  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|)})$.

Data Structures and Algorithms;Combinatorics