×

Integer linear programming formulations for double Roman domination problem. (English) Zbl 1501.90050

Summary: For a graph \(G=(V,E)\), a double Roman dominating function (DRDF) is a function \(f:V \to \{0,1,2,3\}\) having the property that if \(f(v)=0\), then vertex \(v\) must have at least two neighbours assigned 2 under \(f\) or at least one neighbour \(u\) with \(f(u)=3\), and if \(f(v)=1\), then vertex \(v\) must have at least one neighbour \(u\) with \(f(u) \geq 2\). In this paper, we consider the double Roman domination problem, which is an optimization problem of finding the DRDF \(f\) such that \(\sum_{v \in V} f(v)\) is minimum. We propose five integer linear programming (ILP) formulations and one mixed integer linear programming formulation with polynomial number of constraints for this problem. Some additional valid inequalities and bounds are also proposed for some of these formulations. Further, we prove that the first four models indeed solve the double Roman domination problem, and the last two models are equivalent to the others regardless of the variable relaxation or usage of a smaller number of constraints and variables. Additionally, we use one ILP formulation to give an \(H(2(\Delta+1))\)-approximation algorithm. All proposed formulations and approximation algorithm are evaluated on randomly generated graphs to compare the performance.

MSC:

90C10 Integer programming
68W25 Approximation algorithms

Software:

NetworkX
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahangar, H. A.; Chellali, M.; Kuziak, D.; Samodivkin, V., On maximal roman domination in graphs, Int. J. Comput. Math., 93, 7, 1093-1102 (2015) · Zbl 1342.05095
[2] Ahangar, H. A.; Haynes, T. W.; Valenzuela-Tripodoro, J., Mixed roman domination in graphs, Bull. Malays. Math. Sci. Soc., 40, 4, 1443-1454 (2017) · Zbl 1386.05129
[3] Ahangar, H. A.; Chellali, M.; Sheikholeslami, S. M., On the double roman domination in graphs, Discrete Appl. Math., 232, 1-7 (2017) · Zbl 1372.05153
[4] Ahangar, H. A.; Amjadi, J.; Chellali, M.; Nazari-Moghaddam, S.; Sheikholeslami, S., Trees with double roman domination number twice the domination number plus two, Iran. J. Sci. Technol. Trans. A Sci. (2018)
[5] Amjadi, J.; Nazari-Moghaddam, S.; Sheikholeslami, S. M.; Volkmann, L., An upper bound on the double roman domination number, J. Combin. Optim., 36, 1, 81-89 (2018) · Zbl 1437.05177
[6] Anu, V.; Lakshmanan, A., Double roman domination number, Discrete Appl. Math., 244, 198-204 (2018) · Zbl 1387.05186
[7] Beeler, R. A.; Haynes, T. W.; Hedetniemi, S. T., Double roman domination, Discrete Appl. Math., 211, 23-29 (2016) · Zbl 1348.05146
[8] Bondy, J.; Murty, U., Graph Therory, GTM 244 (2008), Springer-Verlag: Springer-Verlag, New York · Zbl 1134.05001
[9] Castorini, E.; Nobili, P.; Triki, C., Optimal routing and resource allocation in multi-hop wireless networks, Optim. Methods Softw., 23, 4, 593-608 (2008) · Zbl 1152.90349
[10] Cecílio, J., Costa, J., and Furtado, P., Survey on data routing in wireless sensor networks, in Wireless Sensor Network Technologies for the Information Explosion Era, Springer, Berlin, Heidelberg, 2010, pp. 3-46.
[11] Chambers, E. W.; Kinnersley, B.; Prince, N.; West, D. B., Extremal problems for roman domination, SIAM J. Discrete Math., 23, 3, 1575-1586 (2009) · Zbl 1207.05135
[12] Chaovalitwongse, W. A.; Berger-Wolf, T. Y.; Dasgupta, B.; Ashley, M. V., Set covering approach for reconstruction of sibling relationships, Optim. Methods Softw., 22, 1, 11-24 (2007) · Zbl 1116.92044
[13] Chellali, M.; Haynes, T. W.; Hedetniemi, S. T.; McRae, A. A., Roman \(####\)-domination, Discrete Appl. Math., 204, 22-28 (2016) · Zbl 1333.05217
[14] Chlebík, M.; Chlebíková, J., Approximation hardness of dominating set problems in bounded degree graphs, Inform. Comput., 206, 1264-1275 (2008) · Zbl 1169.68037
[15] Cockayne, E. J.; Dreyer Jr, P. A.; Hedetniemi, S. M.; Hedetniemi, S. T., Roman domination in graphs, Discrete Math., 278, 1-3, 11-22 (2004) · Zbl 1036.05034
[16] Das, B. and Bharghavan, V., Routing in ad-hoc networks using minimum connected dominating sets, 1997 IEEE International Conference Communications, 1997. ICC’97 Montreal, Towards the Knowledge Millennium, Montreal, Quebec, Canada, 1997, Vol. 1, pp. 376-380.
[17] Dobson, G., Worst-case analysis of greedy heuristics for integer programming with nonnegative data, Math. Oper. Res., 7, 4, 515-531 (1982) · Zbl 0498.90061
[18] Dreyer, P.A., Applications and variations of domination in graphs, Diss., Rutgers University, 2000.
[19] Goddard, W.; Henning, M. A., Independent domination in graphs: A survey and recent results, Discrete Math., 313, 7, 839-854 (2013) · Zbl 1260.05113
[20] Hagberg, A.A., Schult, D.A., and Swart, P.J., Exploring network structure, dynamics, and function using NetworkX, Proceedings of the 7th Python in Science Conference (SciPy2008), G. Varoquaux, T. Vaught, and J. Millman, eds., Pasadena, CA, 2008, pp. 11-15.
[21] Hajibaba, M.; Rad, N. J., Some notes on the roman domination number and italian domination number in graphs, J. Phys. Conf. Ser., 890, 1 (2017)
[22] Hao, G.; Chen, X.; Volkmann, L., Double roman domination in digraphs, Bull. Malays. Math. Sci. Soc., 42, 5, 1907-1920 (2017) · Zbl 1419.05091
[23] Hedetniemi, S.; Slater, P.; Haynes, T. W., Fundamentals of Domination in Graphs (2013), CRC press: CRC press, Boca Raton, FL
[24] Henning, M. A., A survey of selected recent results on total domination in graphs, Discrete Math., 309, 1, 32-63 (2009) · Zbl 1219.05121
[25] Ivanović, M., Improved mixed integer linear programing formulations for roman domination problem, Publ. Inst. Math., 99, 113, 51-58 (2016) · Zbl 1461.65158
[26] Jiang, H., Wu, P., Shao, Z., Rao, Y. and Liu, J., The double roman domination numbers of generalized petersen graphs \(####\), Mathematics6(10) (2018), pp. 206. · Zbl 1515.05139
[27] Ma, Y.; Cai, Q.; Yao, S., Integer linear programming models for the weighted total domination problem, Appl. Math. Comput., 358, 146-150 (2019) · Zbl 1418.34025
[28] Mercier, H.; Bhargava, V. K.; Tarokh, V., A survey of error-correcting codes for channels with symbol synchronization errors, IEEE Commun. Surv. Tutor, 12, 1, 87-96 (2010)
[29] Mobaraky, B. P.; Sheikholeslami, S. M., Bounds on Roman domination numbers of graphs, Mat. vesnik, 60, 4, 247-253 (2008) · Zbl 1274.05359
[30] Rad, N. J.; Rahbani, H., Some progress on the double roman domination in graphs, Discuss. Math. Graph Theory, 39, 1, 41-53 (2019) · Zbl 1401.05224
[31] ReVelle, C. S.; Rosing, K. E., Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly, 107, 7, 585-594 (2000) · Zbl 1039.90038
[32] Stewart, I., Defend the roman empire!, Sci. Amer., 281, 6, 136-138 (1999)
[33] Tural, M. K., Maximal matching polytope in trees, Optim. Methods Softw., 31, 3, 471-478 (2016) · Zbl 1342.90099
[34] Volkmann, L., Double roman domination and domatic numbers of graphs, Commun. Comb. Optim., 3, 71-77 (2018) · Zbl 1384.05128
[35] Yue, J.; Wei, M.; Li, M.; Liu, G., On the double roman domination of graphs, Appl. Math. Comput., 338, 669-675 (2018) · Zbl 1427.05171
[36] Zhang, X.; Li, Z.; Jiang, H.; Shao, Z., Double roman domination in trees, Inform. Process. Lett., 134, 31-34 (2018) · Zbl 1476.05162
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.