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 \rightarrow \lbrace 0, 1, 2 \rbrace$ 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 $N_G(v)$ with weight $2$, or at least two vertices $x, y$ in $N_G(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 $\sum_{p \in V} h(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(\Delta - 0.5) + 1.5)$-approximation algorithm for the MTR2DP and show that the same cannot have $(1 - \delta) \ln |V|$ ratio approximation algorithm  for any $\delta > 0$ unless $P = NP$.  Next, we show that MTR2DP is APX-hard for graphs with $ \Delta=4$.  Finally, we show that the domination and TR2DF problems are not equivalent in computational complexity aspects.

Keywords

Main Subjects

References

[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.
Communications in Combinatorics and Optimization
Volume 7, Issue 2
December 2022
Pages 183-192

Files

Share

How to cite

Statistics