Algorithmic aspects of total Roman {2}-domination in graphs

Document Type : Original paper

Authors

National Institute of Technology, Warangal

Abstract

For a simple, undirected, connected graph G, a function h:V{0,1,2} is called a total Roman {2}-dominating function (TR2DF) if for every vertex v in V with weight 0, either there exists a vertex u in NG(v) with weight 2, or at least two vertices x,y in NG(v) each with weight 1, and the subgraph induced by the vertices with weight more than zero has no isolated vertices. The weight of TR2DF h is pVh(p). The problem of determining  TR2DF of minimum weight is called minimum total Roman \{2\}-domination problem (MTR2DP). We show that MTR2DP is polynomial time solvable for bounded treewidth graphs, threshold graphs and chain graphs. We design a 2(ln(Δ0.5)+1.5)-approximation algorithm for the MTR2DP and show that the same cannot have (1δ)ln|V| ratio approximation algorithm  for any δ>0 unless P=NP.  Next, we show that MTR2DP is APX-hard for graphs with Δ=4.  Finally, we show that the domination and TR2DF problems are not equivalent in computational complexity aspects.

Keywords

Main Subjects


[1] H. Abdollahzadeh Ahangar, M. Chellali, M. Hajjari, and S.M. Sheikholeslami, Further progress on the total Roman {2}-domination number of graphs, Bull. Iranian Math. Soc. (In press).
[2] H. Abdollahzadeh Ahangar, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, Total Roman {2}-dominating functions in graphs, Discuss. Math. Graph Theory (In press).
[3] P. Alimonti and V. Kann, Some APX-completeness results for cubic graphs, Theor. Comput. Sci. 237 (2000), no. 1-2, 123–134.
[4] F. Alizadeh, H.R. Maimani, L.P. Majd, and M.R. Parsa, Roman {2}-domination in graphs and graph products, Iran. J. Math. Sci. Inform. (In press).
[5] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A. McRae, Roman {2}-domination, Discrete Appl. Math. 204 (2016), 22–28.
[6] H. Chen and C. Lu, A note on Roman {2}-domination problem in graphs, arXiv preprint arXiv:1804.09338 (2018).
[7] M.Chlebík  and J.Chlebíková, Approximation hardness of dominating set problems in bounded degree graphs, Inf. Comput. 206 (2008), no. 11, 1264–1275.
[8] B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inf. comput. 85 (1990), no. 1, 12–75.
[9] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, CRC press, 1998.
[10] M.A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs, Theor. Comput. Sci. 766 (2019), 46–57.
[11] M.A. Henning and A. Yeo, Total Domination in Graphs, Springer, 2013.
[12] D.S. Johnson and M.R. Garey, Computers and intractability: A guide to the theory of NP-completeness, Freeman, New York, 1979.
[13] N.V.R. Mahadev and U.N. Peled, Threshold Graphs and Related Topics, Elsevier, 1995.
[14] C. Padamutham and V.S.R. Palagiri, Complexity of Roman {2}-domination and the double Roman domination in graphs, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 1081–1086.
[15] B.S. Panda and A. Pandey, Algorithm and hardness results for outer-connected dominating set in graphs, J. Graph Algorithms Appl. 18 (2014), no. 4, 493–513.
[16] B.S. Panda, A. Pandey, and S. Paul, Algorithmic aspects of b-disjunctive domination in graphs, J. Comb. Optim. 36 (2018), no. 2, 572–590.
[17] C.H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. Syst. Sci. 43 (1991), no. 3, 425–440.
[18] R. Uehara and Y. Uno, Efficient algorithms for the longest path problem, International symposium on algorithms and computation, Springer, 2004, pp. 871–883.
[19] D.B. West, Introduction to Graph Theory, Second Edition, Prentice Hall, 2001.
[20] P. Wu, Z. Li, Z. Shao, and S.M. Sheikholeslami, Trees with equal Roman {2}-domination number and independent Roman {2}-domination number, RAIROOper. Res. 53 (2019), no. 2, 389–400.
[21] M. Yannakakis, Node-and edge-deletion NP-complete problems, Proceedings of the tenth annual ACM symposium on Theory of computing, 1978, pp. 253–264.
[22] J. Zhu, Approximation for minimum total dominating set, Proceedings of the 2nd international conference on interaction sciences: information technology, culture and human, 2009, pp. 119–124.