Liars 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 liars dominating set if (1) ( 1 ) for all v?V(G) v ? V ( G ) , |NG[v]?L|?2 | N G [ 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 | ( N G [ u ] ? N G [ v ] ) ? L | ? 3 . A graph G=(V,E) G = ( V , E ) admits a liars 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 K K , the liars domination decision problem  (LR-DOMDP) is to decide whether G G has a liars dominating set of cardinality at most K K . Slater [P.J. Slater, Liars Domination, Networks, 54(2) (2009) 7074] proved that the LR-DOMDP is NP-complete for general graphs. Subsequently, Roden and Slater [M.L. Roden and P.J. Slater, Liars domination in graphs, Discrete Math., 309(19) (2009) 58845890] showed a more general family of problems to each be NP-complete for bipartite graphs. Besides this result, no other algorithmic result for the liars 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 liars dominating set in a tree.
liars domination domination np-completeness graph algorithm