×

Exact algorithms for weak Roman domination. (English) Zbl 1395.05168

Summary: We consider the weak Roman domination problem. Given an undirected graph \(G = (V, E)\), the aim is to find a weak Roman domination function (wrd-function for short) of minimum cost, i.e. a function \(f : V \rightarrow \{0, 1, 2 \}\) such that every vertex \(v \in V\) is defended (i.e. there exists a neighbor \(u\) of \(v\), possibly \(u = v\), such that \(f(u) \geqslant 1\)) and for every vertex \(v \in V\) with \(f(v) = 0\) there exists a neighbor \(u\) of \(v\) such that \(f(u) \geqslant 1\) and the function \(f_{u \rightarrow v}\) defined by \(f_{u \rightarrow v}(v) = 1\), \(f_{u \rightarrow v}(u) = f(u) - 1\) and \(f_{u \rightarrow v}(x) = f(x)\) otherwise does not contain any undefended vertex. The cost of a wrd-function \(f\) is defined by \(\mathrm{cost}(f) = \sum_{v \in V} f(v)\). The trivial enumeration algorithm runs in time \(\mathcal{O}^\ast(3^n)\) and polynomial space and is the best one known for the problem so far. We are breaking the trivial enumeration barrier by providing two faster algorithms: we first prove that the problem can be solved in \(\mathcal{O}^\ast(2^n)\) time needing exponential space, and then describe an \(\mathcal{O}^\ast(2.227 9^n)\) algorithm using polynomial space. Our results rely on structural properties of a wrd-function, as well as on the best polynomial space algorithm for the red-blue dominating set problem. Moreover we show that the problem can be solved in linear-time on interval graphs.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chambers, E.; Kinnersley, B.; Prince, N.; West, D., Extremal problems for Roman domination, SIAM J. Discrete Math., 23, 3, 1575-1586, (2009) · Zbl 1207.05135
[2] Chapelle, M.; Cochefert, M.; Couturier, J.; Kratsch, D.; Liedloff, M.; Perez, A., Exact algorithms for weak Roman domination, (Lecroq, T.; Mouchard, L., Combinatorial Algorithms - 24th International Workshop, IWOCA, 2013, Rouen, France, July 10-12, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8288, (2013), Springer), 81-93 · Zbl 1408.68112
[3] Chellali, M.; Rad, N.; Volkmann, L., Some results on Roman domination edge critical graphs, AKCE Int. J. Graphs Comb., 9, 2, 195-203, (2012) · Zbl 1257.05113
[4] Cockayne, E.; Favaron, O.; Mynhardt, C., Secure domination, weak Roman domination and forbidden subgraphs, Bull. Inst. Combin. Appl., 39, 87-100, (2003) · Zbl 1051.05065
[5] Cockayne, E.; Grobler, P.; Gründlingh, W.; Munganga, J.; van Vuuren, J., Protection of a graph, Util. Math., 67, 19-32, (2005) · Zbl 1081.05083
[6] Cockayne, E.; Jr, P. D.; Hedetniemi, S. Hedetniemi, S., Roman domination in graphs, Discrete Math., 278, 1-3, 11-22, (2004) · Zbl 1036.05034
[7] Favaron, O.; Karami, K.; Khoeilar, R.; Sheikholeslami, S., On the Roman domination number of a graph, Discrete Math., 309, 3447-3451, (2009) · Zbl 1191.05071
[8] Fomin, F.; Grandoni, F.; Kratsch, D., A measure & conquer approach for the analysis of exact algorithms, J. ACM, 56, 5, (2009) · Zbl 1325.68311
[9] Garey, M.; Johnson, D., Computers and Intractability, (1979), Freeman
[10] Goddard, W.; Hedetniemi, S.; Hedetniemi, S., Eternal security in graphs, J. Combin. Math. Combin. Comput., 52, 160-180, (2005) · Zbl 1067.05051
[11] Goldwasser, J.; Klostermeyer, W., Tight bounds for eternal dominating sets in graphs, Discrete Math., 308, 2589-2593, (2008) · Zbl 1169.05035
[12] Grobler, P.; Mynhardt, C., Secure domination critical graphs, Discrete Math., 309, 5820-5827, (2009) · Zbl 1189.05126
[13] Haynes, T.; Hedetniemi, S.; Slater, P., (Domination in Graphs: Advanced Topics, Pure and Applied Mathematics, vol. 209, (1998), Marcel Dekker Inc) · Zbl 0883.00011
[14] Henning, M. A.; Hedetniemi, S. T., Defending the Roman empire-a new strategy, Discrete Math., 266, 1-3, 239-251, (2003) · Zbl 1024.05068
[15] Hsu, W.; Tsai, K., Linear time algorithms on circular-arc graphs, Inform. Process. Lett., 40, 3, 123-129, (1991) · Zbl 0748.68044
[16] Iwata, Y., A faster algorithm for dominating set analyzed by the potential method, (IPEC’11, Proceedings of the 11th International Symposium on Parameterized and Exact Computation, LNCS, vol. 7112, (2011)), 41-54 · Zbl 1352.68111
[17] Liedloff, M., Algorithmes exacts et exponentiels pour LES problèmes NP-difficiles: domination, variantes et généralisations, (LaboratoireD’Informatique Théorique et Appliquée, (2007), Université Paul Verlaine Metz), (Ph.d. thesis)
[18] Liedloff, M., Finding a dominating set on bipartite graphs, Inform. Process. Lett., 107, 5, 154-157, (2008) · Zbl 1185.05111
[19] Liedloff, M.; Kloks, T.; Liu, J.; Peng, S., Efficient algorithms for Roman domination on some classes of graphs, Discrete Appl. Math., 156, 18, 3400-3415, (2008) · Zbl 1180.05113
[20] Liu, C.-H.; Chang, G., Roman domination on 2-connected graphs, SIAM J. Discrete Math., 26, 1, 193-205, (2012) · Zbl 1245.05100
[21] C.-S. Liu, S.-L. Peng, C.Y. Tang, Weak roman domination on block graphs, in: Proceedings of the 27th Workshop on Combinatorial Mathematics and Computation Theory, Providence University, Taichung, Taiwan, April 30-May 1, 2010, 2010, pp. 86-89.; C.-S. Liu, S.-L. Peng, C.Y. Tang, Weak roman domination on block graphs, in: Proceedings of the 27th Workshop on Combinatorial Mathematics and Computation Theory, Providence University, Taichung, Taiwan, April 30-May 1, 2010, 2010, pp. 86-89.
[22] Mai, T. N.M. M.; Pushpam, P. R.L., Weak Roman domination in graphs, Discuss. Math. Graph Theory, 31, 1, 161-170, (2011) · Zbl 1284.05201
[23] ReVelle, C.; Rosing, K., Defendens imperium romanum: a classical problem in military strategy, Math. Assoc. Amer., 107, 7, 585-594, (2000) · Zbl 1039.90038
[24] Spinrad, J., (Efficient Graph Representations, Fields Institute Monographs, (2003), American Mathematical Soc)
[25] Stewart, I., Defend the Roman empire!, Sci. Am., 281, 6, 136-139, (1999)
[26] van Rooij, J., Exact Exponential-Time Algorithms for Domination Problems in Graphs, (2011), Utrecht University Netherlands, (Ph.d. thesis)
[27] van Rooij, J.; Bodlaender, H., Exact algorithms for dominating set, Discrete Appl. Math., 159, 17, 2147-2164, (2011) · Zbl 1237.05157
[28] Xing, H.-M.; Chen, X.; Chen, X.-G., A note on Roman domination in graphs, Discrete Math., 306, 3338-3340, (2006) · Zbl 1108.05072
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.