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

NP-completeness Results for Partitioning a Graph into Total Dominating Sets

  • Conference paper
  • First Online:
Computing and Combinatorics (COCOON 2017)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10392))

Included in the following conference series:

Abstract

A total domatic k-partition of a graph is a partition of its vertex set into k subsets such that each intersects the open neighborhood of each vertex. The maximum k for which a total domatic k-partition exists is known as the total domatic number of a graph G, denoted by \(d_t(G)\). We extend considerably the known hardness results by showing it is \(\textsc {NP}\)-complete to decide whether \(d_t(G) \ge 3\) where G is a bipartite planar graph of bounded maximum degree. Similarly, for every \(k \ge 3\), it is \(\textsc {NP}\)-complete to decide whether \(d_t(G) \ge k\), where G is a split graph or k-regular. In particular, these results complement recent combinatorial results regarding \(d_t(G)\) on some of these graph classes by showing that the known results are, in a sense, best possible. Finally, for general n-vertex graphs, we show the problem is solvable in \(2^n n^{O(1)}\) time, and derive even faster algorithms for special graph classes.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Abbas, W., Egerstedt, M., Liu, C.H., Thomas, R., Whalen, P.: Deploying robots with two sensors in \(K_{1,6}\)-free graphs. J. Graph Theor. 82(3), 236–252 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  2. Akbari, S., Motiei, M., Mozaffari, S., Yazdanbod, S.: Cubic graphs with total domatic number at least two. arXiv preprint arXiv:1512.04748 (2015)

  3. Björklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546–563 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bollobás, B., Cockayne, E.J.: Graph-theoretic parameters concerning domination, independence, and irredundance. J. Graph Theor. 3(3), 241–249 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  6. Chen, B., Kim, J.H., Tait, M., Verstraete, J.: On coupon colorings of graphs. Discr. Appl. Math. 193, 94–101 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cockayne, E.J., Dawes, R.M., Hedetniemi, S.T.: Total domination in graphs. Networks 10(3), 211–219 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  8. Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameter. Algorithms. Springer, Heidelberg (2015)

    Book  MATH  Google Scholar 

  9. Dai, F., Wu, J.: An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans. Parallel Distrib. Syst. 15(10), 908–920 (2004)

    Article  Google Scholar 

  10. Diestel, R.: Graph Theory. Springer, Heidelberg (2010)

    Book  MATH  Google Scholar 

  11. Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A.: Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1), 9:1–9:17 (2008)

    Article  MathSciNet  Google Scholar 

  12. Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237–267 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  13. Gaspers, S., Lee, E.: Faster graph coloring in polynomial space. ArXiv e-prints arXiv:1607.06201 (2016)

  14. Goddard, W., Henning, M.A.: Thoroughly distributed colorings. arXiv preprint arXiv:1609.09684 (2016)

  15. Guruswami, V., Lee, E.: Strong inapproximability results on balanced rainbow-colorable hypergraphs. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 822–836. SIAM (2015)

    Google Scholar 

  16. Han, B., Jia, W.: Clustering wireless ad hoc networks with weakly connected dominating set. J. Parallel Distrib. Comput. 67(6), 727–737 (2007)

    Article  MATH  Google Scholar 

  17. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in Graphs: Advanced Topics. Marcel Dekker Inc., New York (1998)

    MATH  Google Scholar 

  18. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. CRC Press, Boca Raton (1998)

    MATH  Google Scholar 

  19. Heggernes, P., Telle, J.A.: Partitioning graphs into generalized dominating sets. Nordic J. Comput. 5(2), 128–142 (1998)

    MathSciNet  MATH  Google Scholar 

  20. Henning, M.A.: A survey of selected recent results on total domination in graphs. Discr. Math. 309(1), 32–63 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  21. Henning, M.A., Yeo, A.: 2-colorings in \(k\)-regular \(k\)-uniform hypergraphs. Eur. J. Comb. 34(7), 1192–1202 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  22. Henning, M.A., Yeo, A.: Total Domination in Graphs. Springer, New York (2013)

    Book  MATH  Google Scholar 

  23. Kaplan, H., Shamir, R.: The domatic number problem on some perfect graph families. Inf. Process. Lett. 49(1), 51–56 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  24. Leven, D., Galil, Z.: NP-completeness of finding the chromatic index of regular graphs. J. Algorithms 4(1), 35–44 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  25. Mahadev, N.V.R., Peled, U.N.: Threshold Graphs and Related Topics, vol. 56. Elsevier, Amsterdam (1995)

    MATH  Google Scholar 

  26. Nederlof, J., van Rooij, J.M.M., van Dijk, T.C.: Inclusion/exclusion meets measure and conquer. Algorithmica 69(3), 685–740 (2014)

    MathSciNet  MATH  Google Scholar 

  27. Pfaff, J., Laskar, R., Hedetniemi, S.T.: NP-completeness of total and connected domination and irredundance for bipartite graphs. Technical report, Clemson University, Department of Mathematical Sciences 428 (1983)

    Google Scholar 

  28. Poon, S.-H., Yen, W.C.-K., Ung, C.-T.: Domatic partition on several classes of graphs. In: Lin, G. (ed.) COCOA 2012. LNCS, vol. 7402, pp. 245–256. Springer, Heidelberg (2012). doi:10.1007/978-3-642-31770-5_22

    Chapter  Google Scholar 

  29. Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic programming on tree decompositions using generalised fast subset convolution. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 566–577. Springer, Heidelberg (2009). doi:10.1007/978-3-642-04128-0_51

    Chapter  Google Scholar 

  30. Shi, Y., Wei, M., Yue, J., Zhao, Y.: Coupon coloring of some special graphs. J. Comb. Optim. 33(1), 156–164 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  31. Stojmenovic, I., Seddigh, M., Zunic, J.: Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks. IEEE Trans. Parallel Distrib. Syst. 13(1), 14–25 (2002)

    Article  Google Scholar 

  32. Zelinka, B.: Total domatic number of cacti. Math. Slovaca 38(3), 207–214 (1988)

    MathSciNet  MATH  Google Scholar 

  33. Zelinka, B.: Total domatic number and degrees of vertices of a graph. Math. Slovaca 39(1), 7–11 (1989)

    MathSciNet  MATH  Google Scholar 

  34. Zelinka, B.: Domination in generalized Petersen graphs. Czech. Math. J. 52(1), 11–16 (2002)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

This work was supported in part by the Academy of Finland, under Grant 276864 (M.K.), and by the Emil Aaltonen Foundation, under Grant 160138 N (J.L.).

Author information

Author notes

  1. Juho Lauri

    Present address: Bell Labs, Dublin, Ireland

Authors and Affiliations

  1. University of Helsinki, Helsinki, Finland

    Mikko Koivisto

  2. Tampere University of Technology, Tampere, Finland

    Petteri Laakkonen & Juho Lauri

Authors
  1. Mikko Koivisto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Petteri Laakkonen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Juho Lauri
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Juho Lauri .

Editor information

Editors and Affiliations

  1. Department of Computing, Hong Kong Polytechnic University, Hong Kong, China

    Yixin Cao

  2. Texas A&M University, College Station, Texas, USA

    Jianer Chen

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Koivisto, M., Laakkonen, P., Lauri, J. (2017). NP-completeness Results for Partitioning a Graph into Total Dominating Sets. In: Cao, Y., Chen, J. (eds) Computing and Combinatorics. COCOON 2017. Lecture Notes in Computer Science(), vol 10392. Springer, Cham. https://doi.org/10.1007/978-3-319-62389-4_28

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-62389-4_28

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-62388-7

  • Online ISBN: 978-3-319-62389-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation