Abstract
A Roman dominating function of graph G is a function \(r: V(G)\rightarrow \{0, 1, 2\}\) satisfying that every vertex v with \(r(v)=0\) is adjacent to at least one vertex u with \(r(u)=2.\) The minimum Roman dominating set problem (MinRDS) is to compute a Roman dominating function r that minimizes the weight \(\sum _{v\in V}r(v).\) The minimum connected Roman dominating set problem (MinCRDS) is to find a minimum weight Roman dominating function \(r_{c}\) such that the subgraph of G induced by \(D_{R}=\{v \in V \mid r_{c}(v)=1 ~\mathrm{{or}}~ r_{c}(v)=2\}\) is connected. In this paper, we present a greedy algorithm for MinRDS with a guaranteed performance ratio at most \(H(\delta _{\max }+1),\) where \(H(\cdot )\) is the Harmonic number and \(\delta _{\max }\) is the maximum degree of the graph. For any \(\varepsilon >0,\) we show that there exists a greedy algorithm for MinCRDS with approximation ratio at most \((1+\varepsilon )\ln \delta _{\max }+O(1).\) The challenge for the analysis of the MinCRDS algorithm lies in the fact that the potential function is not only non-submodular but also non-monotone.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Antoaneta, K., Ivona, P.: Roman domination number on cardinal product of paths and cycles. Kragujev. J. Math. 6(1), 71–78 (2015)
Chambers, E.W., Kinnersley, B., Prince, N., West, D.B.: Extremal problems for roman domination. SIAM J. Discrete Math. 23, 1575–1586 (2010)
Cockayne, E.J., Dreyer, P.A., Hedetniemi, S.M., Hedetniemi, S.T.: Roman domination in graphs. Discrete Math. 278(1–3), 11–22 (2000)
Cockayne, E.J., Grobler, P.J.P., Gründlingh, W.R., Munganga, J., van Vuuren, J.H.: Protection of a graph. Util. Math. 67, 19–32 (2005)
Dreyer, P.A.: Applications and variations of domination in graphs. Ph.D. thesis, Rutgers University, New Jersey (2000)
Du, D.Z., Ko, K.I., Hu, X.: Design and Analysis of Approximation Algorithms. Springer, Berlin (2012)
Fu, X.L., Yang, Y.S., Jiang, B.Q.: Roman domination in regular graphs. Discrete Math. 309(6), 1528–1537 (2009)
Lideloff, M., Kloks, T., Liu, J., Peng, S.L.: Roman domination over some graph classes. In: Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 3787, pp. 103–114. Springer, Berlin (2005)
Liu, C.H., Chang, G.J.: Roman domination on strongly chordal graphs. J. Comb. Optim. 26(3), 608–619 (2013)
Naresh Kumar, H., Pradhan, D., Venkatakrishnan, Y.B.: Double vertex-edge domination in graphs: complexity and algorithms. J. Appl. Math. Comput. 66, 245–262 (2021)
Padamutham, C., Palagiri, V.: Algorithmic aspects of Roman domination in graphs. J. Appl. Math. Comput. 64(1–2), 89–102 (2020)
Pagourtzis, A., Penna, P., Schlude, K., Steinhofel, K., Taylor, D., Widmayer, P.: Server placements, Roman domination and other dominating set variants. In: Proceedings of Second International Conference on Theoretical Computer Science, pp. 280–291 (2002)
Raczek, J., Cyman, J.: Weakly connected Roman domination in graphs. Discrete Appl. Math. 267, 151–159 (2019)
Shang, W., Wang, X., Hu, X.: Roman domination and its variants in unit disk graphs. Discrete Math. Algorithms Appl. 2(01), 99–105 (2010)
Stewart, I.: Defend the Roman empire! Sci. Am. 281(6), 136–138 (1999)
Šumenjak, T.K., Pavlič, P., Tepeh, A.: On the Roman domination in the lexicographic product of graphs. Discrete Appl. Math. 160(13–14), 2030–2036 (2012)
Wang, L., Shi, Y., Zhang, Z., Zhang, Z.-B., Zhang, X.: Approximation algorithm for a generalized Roman domination problem in unit ball graphs. J. Comb. Optim. 39, 138–148 (2020)
Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385–393 (1982)
Acknowledgements
This research is supported by NSFC (U20A2068, 11901533, 11771013), and ZJNSFC (LD19A010001).
Author information
Authors and Affiliations
Corresponding authors
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Li, K., Ran, Y., Zhang, Z. et al. Nearly tight approximation algorithm for (connected) Roman dominating set. Optim Lett 16, 2261–2276 (2022). https://doi.org/10.1007/s11590-022-01862-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-022-01862-0