Hardness results and approximation algorithm for total liars domination in graphs
In this paper, we initiate the study of total liars domination of a graph. Asubset L?V of a graph G=(V,E) is called a total liars dominating set of G if (i) for all v?V, |N G (v)?L|?2 and (ii) for every pair u,v?V of distinct vertices, |(N G (u)?N G (v))?L|?3. The total liars domination number of a graph G is the cardinality of a minimum total liars dominating set of G and is denoted by ? TLR (G). The Minimum Total Liars Domination Problem is to find a total liars dominating set of minimum cardinality of the input graph G. Given a graph G and a positive integer k, the Total Liars Domination Decision Problem is to check whether G has a total liars dominating set of cardinality at most k. In this paper, we give a necessary and sufficient condition for the existence of a total liars dominating set in a graph. We show that the Total Liars Domination Decision Problem is NP-complete for general graphs and is NP-complete even for split graphs and hence for chordal graphs. We also propose a 2(ln?(G)+1)-approximation algorithm for the Minimum Total Liars Domination Problem, where ?(G) is the maximum degree of the input graph G. We show that Minimum Total Liars Domination Problem cannot be approximated within a factor of \((\frac{1}{8}-\epsilon)\ln(|V|)\) for any ?>0, unless NP?DTIME(|V|loglog|V|). Finally, we show that Minimum Total Liars Domination Problem is APX-complete for graphs with bounded degree 4.
approximation algorithm liars domination domination np-completeness chordal graph apx-completeness graph algorithm