Algorithmic complexity of triple Roman dominating functions on graphs

Document Type : Original paper

Authors

Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran

Abstract

Given a graph $G=(V,E)$,  a  function  $f:V\to \{0,1,2,3,4\}$ is a triple Roman  dominating function (TRDF)  of $G$, for each vertex $v\in V$,  (i) if $f (v ) = 0 $, then  $v$ must have either one neighbour in $V_4$, or either two neighbours in $V_2 \cup  V_3$ (one neighbour in $V_3$) or either three neighbours in $V_2 $, (ii) if $f (v ) = 1 $, then $v$ must have either one neighbour in  $V_3 \cup  V_4$  or either two neighbours in $V_2 $, and if $f (v ) = 2 $, then $v$ must have one neighbour in $V_2 \cup  V_3\cup  V_4$. The triple Roman  domination number of $G$ is the  minimum weight of an TRDF  $f$  of $G$, where the weight of $f$ is $\sum_{v\in V}f(v)$.  The triple  Roman  domination problem is to compute the  triple Roman  domination number of a given graph.  In this paper, we study the triple  Roman  domination problem. We show that   the problem is NP-complete for  the  star convex bipartite  and the   comb convex bipartite graphs and is APX-complete for graphs of degree at~most~4. We propose a linear-time algorithm for computing  the triple Roman  domination number of proper interval graphs.  We also   give an $( 2 H(\Delta(G)+1) -1  )$-approximation algorithm  for solving the problem  for any graph $G$,  where   $  \Delta(G)$ is the maximum degree of $G$ and $H(d)$ denotes the first $d$ terms of the harmonic  series. In addition, we prove  that  for any $\varepsilon>0$  there is no  $(1/4-\varepsilon)\ln|V|$-approximation  polynomial-time   algorithm for solving  the problem on bipartite and split  graphs, unless NP $\subseteq$ DTIME $(|V|^{O(\log\log|V |)})$.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, M.P. ´Alvarez, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, Triple Roman domination in graphs, Applied Math. Comput. 391 (2021), Article ID: 125444. https://doi.org/10.1016/j.amc.2020.125444
[2] H. Abdollahzadeh Ahangar, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, Total Roman {2}-ominating functions in graphs, Discuss. Math. Graph Theory 42 (2022), no. 3, 937–958. https://doi.org/10.7151/dmgt.2316
[3] P. Alimonti and V. Kann, Some APX-completeness results for cubic graphs, Theoretical Comput. Sci. 237 (2000), no. 1-2, 123–134. https://doi.org/10.1016/S0304-3975(98)00158-3
[4] J. Amjadi and H. Sadeghi, Triple Roman domination subdivision number in graphs., Comput. Sci. J. Moldova 30 (2022), no. 1, 109–130.
[5] T. Araki and H. Miyazaki, Secure domination in proper interval graphs, Discrete Appl. Math. 247 (2018), 70–76. https://doi.org/10.1016/j.dam.2018.03.040
[6] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29. https://doi.org/10.1016/j.dam.2016.03.017
[7] K.S. Booth and G.S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci. 13 (1976), no. 3, 335–379. https://doi.org/10.1016/S0022-0000(76)80045-1
[8] M. Chlebík and J. Chlebíková, Approximation hardness of dominating set problems in bounded degree graphs, Inform. Comput. 206 (2008), no. 11, 1264–1275. https://doi.org/10.1016/j.ic.2008.07.003
[9] M. Hajjari, H. Abdollahzadeh Ahangar, R. Khoeilar, Z. Shao, and S.M. Sheikholeslami, New bounds on the triple Roman domination number of graphs, J. Math. 2022 (2022), Artice ID: 9992618. https://doi.org/10.1155/2022/9992618
[10] M. Hajjari, H. Abdollahzadeh Ahangar, R. Khoeilar, Z. Shao, and S.M. Sheikholeslami, An upper bound on triple Roman domination, Commun. Comb. Optim. 8 (2023), no. 3, 505–511. https://doi.org/10.22049/cco.2022.27816.1359
[11] D.S. Johnson and M.R. Garey, Computers and intractability: A guide to the theory of NP-completeness, W.H. Freeman, New York, 1979.
[12] M.S. Lin and C.M. Chen, Counting independent sets in tree convex bipartite graphs, Discrete Appl. Math. 218 (2017), 113–122. https://doi.org/10.1016/j.dam.2016.08.017
[13] P.J. Looges and S. Olariu, Optimal greedy algorithms for indifference graphs, Comput. Math. Appl. 25 (1993), no. 7, 15–25. https://doi.org/10.1016/0898-1221(93)90308-I
[14] F. Nahani Pour, H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, Global triple Roman dominating function, Discrete Appl. Math. 314 (2022), 228–237. https://doi.org/10.1016/j.dam.2022.02.015
[15] C.H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. System Sci. 43 (1991), no. 3, 425–440. https://doi.org/10.1016/0022-0000(91)90023-X
[16] A. Poureidi, Double Roman domination in graphs: algorithmic complexity, Commun. Comb. Optim. 8 (2023), no. 3, 491–503. https://doi.org/10.22049/cco.2022.27661.1309
[17] L. Volkmann, Double Roman domination and domatic numbers of graphs, Commun. Comb. Optim. 3 (2018), no. 1, 71–77. https://doi.org/10.22049/cco.2018.26125.1078
Communications in Combinatorics and Optimization
Volume 9, Issue 2
June 2024
Pages 217-232

Files

Share

How to cite

Statistics