Liar’s domination in graphs: Complexity and algorithm

A set L⊆V(G)L⊆V(G) of a graph G=(V,E)G=(V,E) is a liar’s dominating set if (1)(1) for all v∈V(G)v∈V(G), |NG[v]∩L|≥2|NG[v]∩L|≥2 and (2)(2) for every pair u,v∈V(G)u,v∈V(G) of distinct vertices, |(NG[u]∪NG[v])∩L|≥3|(NG[u]∪NG[v])∩L|≥3. A graph G=(V,E)G=(V,E) admits a liar’s dominating set if each of its connected component has at least three vertices. Given a graph G=(V,E)G=(V,E) and an integer KK, the liar’s domination decision problem   (LR-DOMDP) is to decide whether GG has a liar’s dominating set of cardinality at most KK. Slater [P.J. Slater, Liar’s Domination, Networks, 54(2) (2009) 70–74] proved that the LR-DOMDP is NP-complete for general graphs. Subsequently, Roden and Slater [M.L. Roden and P.J. Slater, Liar’s domination in graphs, Discrete Math., 309(19) (2009) 5884–5890] showed a more general family of problems to each be NP-complete for bipartite graphs. Besides this result, no other algorithmic result for the liar’s dominating set problem is available in the literature. In this paper, we first strengthen the complexity result of the LR-DOMDP by showing that this problem remains NP-complete for split graphs and hence for chordal graphs. Finally, we propose a linear time algorithm for computing a minimum cardinality liar’s dominating set in a tree.