Hardness results and approximation algorithm for total liar’s domination in graphs

B. S. Panda () and Satya Paul
Additional contact information
B. S. Panda: Indian Institute of Technology Delhi

Journal of Combinatorial Optimization, 2014, vol. 27, issue 4, No 2, 643-662

Abstract: Abstract In this paper, we initiate the study of total liar’s domination of a graph. A subset L⊆V of a graph G=(V,E) is called a total liar’s 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 liar’s domination number of a graph G is the cardinality of a minimum total liar’s dominating set of G and is denoted by γ TLR (G). The Minimum Total Liar’s Domination Problem is to find a total liar’s dominating set of minimum cardinality of the input graph G. Given a graph G and a positive integer k, the Total Liar’s Domination Decision Problem is to check whether G has a total liar’s dominating set of cardinality at most k. In this paper, we give a necessary and sufficient condition for the existence of a total liar’s dominating set in a graph. We show that the Total Liar’s 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 Liar’s Domination Problem, where Δ(G) is the maximum degree of the input graph G. We show that Minimum Total Liar’s 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 Liar’s Domination Problem is APX-complete for graphs with bounded degree 4.

Keywords: Domination; Liar’s domination; Chordal graph; Graph algorithm; Approximation algorithm; NP-completeness; APX-completeness (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9542-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:27:y:2014:i:4:d:10.1007_s10878-012-9542-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9542-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().