Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

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

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Algorithm 1
Fig. 3
Fig. 4

Similar content being viewed by others

References

  • Alimonti P, Kann V (2000) Some APX-completeness results for cubic graphs. Theor Comput Sci 237(1–2):123–134

    Article  MATH  MathSciNet  Google Scholar 

  • Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M (1999) Complexity and approximation. Springer, Berlin

    Book  MATH  Google Scholar 

  • Bertossi AA (1986) Total domination in interval graphs. Inf Process Lett 23(3):131–134

    Article  MATH  MathSciNet  Google Scholar 

  • Bowie MR (2008) Liar’s domination and the domination continuum. PhD thesis, University of Alabama in Huntsville

  • Brandstädt A, Kratsch D (1987) On domination problems for permutation and other graphs. Theor Comput Sci 54(2–3):181–198

    Article  MATH  Google Scholar 

  • Chang GJ (1988) Labeling algorithms for domination problems in sun-free chordal graphs. Discrete Appl Math 22(1):21–34

    Article  MATH  MathSciNet  Google Scholar 

  • Chang GJ (1989) Total domination in block graphs. Oper Res Lett 8(1):53–57

    Article  MATH  MathSciNet  Google Scholar 

  • Chlebík M, Chlebíková J (2008) Approximation hardness of dominating set problems in bounded degree graphs. Inf Comput 206(11):1264–1275

    Article  MATH  Google Scholar 

  • Cockayne EJ, Dawes RM, Hedetniemi ST (1980) Total domination in graphs. Networks 10(3):211–219

    Article  MATH  MathSciNet  Google Scholar 

  • Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT Press/McGraw-Hill, Cambridge/New York

    MATH  Google Scholar 

  • Gimbel J, Mahéo M, Virlouvet C (1997) Double total domination of graphs. Discrete Math 165–166:343–351

    Article  Google Scholar 

  • Harary F, Haynes TW (2000) Double domination in graphs. Ars Comb 55:201–213

    MATH  MathSciNet  Google Scholar 

  • Haynes TW, Hedetniemi ST, Slater PJ (1998a) Fundamentals of domination in graphs. Dekker, New York

    MATH  Google Scholar 

  • Haynes TW, Hedetniemi ST, Slater PJ (1998b) Domination in graphs, advanced topics. Dekker, New York

    MATH  Google Scholar 

  • Henning MA (2009) A survey of selected recent results on total domination in graphs. Discrete Math 309(1):32–63

    Article  MATH  MathSciNet  Google Scholar 

  • Henning MA, Kazemi AP (2010) k-tuple total domination in graphs. Discrete Appl Math 158(9):1006–1011

    Article  MATH  MathSciNet  Google Scholar 

  • Karp RM (1972) Reducibility among combinatorial problems. In: Complexity of computer computations, New York, pp 85–103

    Chapter  Google Scholar 

  • Klasing R, Laforest C (2004) Hardness results and approximation algorithms of k-tuple domination in graphs. Inf Process Lett 89:75–83

    Article  MATH  MathSciNet  Google Scholar 

  • Laskar R, Pfaff J, Hedetniemi SM, Hedemiemi ST (1984) On the algorithmic complexity of total domination. SIAM J Algebr Discrete Methods 5:420–425

    Article  MATH  Google Scholar 

  • Liao CS, Chang GJ (2002) Algorithmic aspects of k-tuple domination in graphs. Taiwan J Math 6(3):420–455

    MathSciNet  Google Scholar 

  • Liao CS, Chang GJ (2003) k-tuple domination in graphs. Inf Process Lett 87(1):45–50

    Article  MATH  MathSciNet  Google Scholar 

  • Pfaff J, Laskar R, Hedetniemi ST (1983) NP-completeness of total and connected domination, and irredundance for bipartite graphs. Tech rept 428, Dept of Mathematical Science, Clemson University

  • Roden ML, Slater PJ (2008) Liar’s domination and the domination continuum. Congr Numer 190:77–85

    MATH  MathSciNet  Google Scholar 

  • Roden ML, Slater PJ (2009) Liar’s domination in graphs. Discrete Math 309(19):5884–5890

    Article  MATH  MathSciNet  Google Scholar 

  • Slater PJ (2009) Liar’s domination. Networks 54(2):70–74

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science and Application Group, Department of Mathematics, Indian Institute of Technology Delhi, Hauz Khas, New Delhi, 110 016, India

    B. S. Panda & S. Paul

Authors
  1. B. S. Panda
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. Paul
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to B. S. Panda.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Panda, B.S., Paul, S. Hardness results and approximation algorithm for total liar’s domination in graphs. J Comb Optim 27, 643–662 (2014). https://doi.org/10.1007/s10878-012-9542-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-012-9542-3

Keywords

Search

Navigation