2025/09/15 by Bhattacharya, Debojyoti, Paul, Subhabrata
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2509.11775
Let G=(V, E) be a simple undirected graph. A closed neighbourhood of an edge e=uv between two vertices u and v of G, denoted by NG[e], is the set of vertices in the neighbourhood of u and v including \u,v\. A subset L of V is said to be liar's vertex-edge dominating set if (i) for every edge e∈ E, |NG[e]∩ L|≥ 2 and (ii) for every pair of distinct edges e,e', |(NG[e]∪ NG[e'])∩ L|≥ 3. The minimum liar's vertex-edge domination problem is to find the liar's vertex-edge dominating set of minimum cardinality. In this article, we show that the liar's vertex-edge domination problem is NP-complete in unit disk graphs, and we design a polynomial time approximation scheme(PTAS) for the minimum liar's vertex-edge domination problem in unit disk graphs.