Algorithmic aspects of Roman $\left\{3\right\}$-domination in graphs

Chakradhar, Padamutham; Venkata Subba Reddy, Palagiri

RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2277-2291

Let G be a simple, undirected graph. A function g : V(G) → {0, 1, 2, 3} having the property that ∑ v g(v)≥3, if g(u) = 0, and ∑ v g(v)≥2, if g(u) = 1 for any vertex u ∈ G, where N$$(u) is the set of vertices adjacent to u in G, is called a Roman {3}-dominating function (R3DF) of G. The weight of a R3DF g is the sum g(V)=∑$$g(v). The minimum weight of a R3DF is called the Roman {3}-domination number and is denoted by γ_{R3}(G). Given a graph G and a positive integer k, the Roman {3}-domination problem (R3DP) is to check whether G has a R3DF of weight at most k. In this paper, first we show that the R3DP is NP-complete for chordal graphs, planar graphs and for two subclasses of bipartite graphs namely, star convex bipartite graphs and comb convex bipartite graphs. The minimum Roman {3}-domination problem (MR3DP) is to find a R3DF of minimum weight in the input graph. We show that MR3DP is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs, a subclass of split graphs. We propose a 3(1 + ln(Δ − 1))-approximation algorithm for the MR3DP, where Δ is the maximum degree of G and show that the MR3DP problem cannot be approximated within (1 − ε)ln|V| for any ε > 0 unless NP ⊆ DTIME(|V|$$). Next, we show that the MR3DP problem is APX-complete for graphs with maximum degree 4. We also show that the domination and Roman {3}-domination problems are not equivalent in computational complexity aspects. Finally, an ILP formulation for MR3DP is proposed.

Classification : 05C69, 68Q25
Keywords: Roman dominating function, Roman {3}-domination, NP-complete, APX-complete, Integer Linear Programming-domination, NP-complete, APX-complete, integer linear programming

[1] H. A. Ahangar, M. Chellali and S. M. Sheikholeslami, On the double Roman domination in graphs. Discrete Appl. Math. 232 (2017) 1–7. | MR | DOI

[2] P. Alimonti and V. Kann, Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237 (2000) 123–134. | MR | DOI

[3] F. Alizade, H. R. Maimani, L. P. Majd and M. R. Parsa, Roman {2}-domination in graphs and graph products. Preprint (2017). | arXiv

[4] V. Anu and S. Aparna Lakshmanan, Double Roman domination number. Discrete Appl. Math. 244 (2018) 198–204. | MR | DOI

[5] M. Chellali, T. W. Haynes, S. T. Hedetniemi and A. A. Mcrae, Roman $\left\{2\right\}$-domination. Discrete Appl. Math. 204 (2016) 22–28. | MR | DOI

[6] M. Chlebík and J. Chlebíková, Approximation hardness of dominating set problems in bounded degree graphs. Inf. Comput. 206 (2008) 1264–1275. | MR | DOI

[7] E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi and S. T. Hedetniemi, Roman domination in graphs. Discrete Math. 278 (2004) 11–22. | MR | DOI

[8] B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85 (1990) 12–75. | MR | DOI

[9] O. Favaron, H. Karami, R. Khoeilar and S. M. Sheikholeslami, On the Roman domination number of a graph. Discrete Math. 309 (2009) 3447–3451. | MR | DOI

[10] M. R. Garey and D. S. Johnson, Computers and Interactability: A Guide to the Theory of NP-completeness. Freeman, New York (1979). | MR

[11] T. W. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs. CRC Press (1998). | MR

[12] M. A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs. Theor. Comput. Sci. 766 (2019) 46–57. | MR | DOI

[13] M. Ivanović, Improved mixed integer linear programing formulations for Roman domination problem. Publications de l’Institut Mathematique 99 (2016) 51–58. | MR | DOI

[14] C. E. Leiserson, R. L. Rivest, T. H. Cormen and C. Stein, Introduction to Algorithms. MIT Press Cambridge, MA (2001). | MR

[15] M. Lin and C. Chen, Counting independent sets in tree convex bipartite graphs. Discrete Appl. Math. 218 (2017) 113–122. | MR | DOI

[16] N. Mahadev and U. Peled, Threshold Graphs and Related Topics. Elsevier (1995). | MR

[17] D. A. Mojdeh and L. Volkmann, Roman $\left\{3\right\}$-domination (double Italian domination). Discrete Appl. Math. 283 (2020) 555–564. | MR | DOI

[18] A. Oganian and D. Josep, On the complexity of optimal microaggregation for statistical disclosure control. Stat. J. United Nations Econ. Commission Eur. 18 (2001) 345–353. | DOI

[19] B. S. Panda and A. Pandey, Algorithm and hardness results for outer-connected dominating set in graphs. J. Graph Algorithms Appl. 18 (2014) 493–513. | MR | DOI

[20] B. S. Panda, A. Pandey and S. Paul, Algorithmic aspects of $b$-disjunctive domination in graphs. J. Comb. Optim. 36 (2018) 572–590. | MR | DOI

[21] C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43 (1991) 425–440. | MR | DOI

[22] N. J. Rad and L. Volkmann, Roman domination perfect graphs. An. Stiint. Univ. Ovidius Constanta Ser. Mat. 19 (2019) 167–174. | MR

[23] C. S. Revelle and K. E. Rosing, Defendens imperium romanum: a classical problem in military strategy. Am. Math. Mon. 107 (2000) 585–594. | MR | DOI

[24] A. Robert, T. W. Haynes and S. T. Hedetniemi, Double Roman domination. Discrete Appl. Math. 211 (2016) 23–29. | MR | DOI

[25] R. Uehara and Y. Uno, Efficient algorithms for the longest path problem. In: International Symposium on Algorithms and Computation. Springer, Berlin (2004) 871–883. | MR

[26] D. B. West, Introduction to Graph Theory. Prentice Hall, Upper Saddle River 92001). | MR

[27] P. Wu, Z. Li, Z. Shao and S. M. Sheikholeslami, Trees with equal Roman $\left\{2\right\}$-domination number and independent Roman $\left\{2\right\}$-domination number. RAIRO: Oper. Res. 53 (2019) 389–400. | MR | DOI

[28] M. YannakakisNode-and edge-deletion NP-complete problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing. STOC, New York, USA (1978) 253–264.