×
Poureidi, Abolfazl; Fathali, Jafar

Algorithmic complexity of triple Roman dominating functions on graphs. (English) Zbl 07814385

Commun. Comb. Optim. 9, No. 2, 217-232 (2024).
Summary: 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|)})\).

Cited in 2 Documents

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Keywords:

triple Roman domination; approximation algorithm; NP-complete; proper interval graph; APX-complete
Cite Review PDF
Full Text: DOI

References:

[1] [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 · Zbl 1462.05266
[2] [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 · Zbl 1492.05109
[3] [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 · Zbl 0939.68052
[4] [4] J. Amjadi and H. Sadeghi, Triple Roman domination subdivision number in graphs., Comput. Sci. J. Moldova 30 (2022), no. 1, 109-130. · Zbl 1535.05206
[5] [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 · Zbl 1394.05085
[6] [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 · Zbl 1348.05146
[7] [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 · Zbl 0367.68034
[8] [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 · Zbl 1169.68037
[9] [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] [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 · Zbl 07812865
[11] [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. · Zbl 0411.68039
[12] [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 · Zbl 1352.05146
[13] [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 · Zbl 0794.68115
[14] [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 · Zbl 1490.05202
[15] [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 · Zbl 0765.68036
[16] [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 · Zbl 07812864
[17] [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 · Zbl 1384.05128
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.