On the k-rainbow domination in graphs with bounded tree-width
Abstract
Given a positive integer k and a graph G = (V, E), a function f from V to the power set of Ik is called a k-rainbow function if for each vertex v ∈ V, f(v)=∅ implies ∪u ∈ N(v)f(u)=Ik where N(v) is the set of all neighbors of vertex v and Ik = {1, …, k}. Finding a k-rainbow function of minimum weight of ∑v ∈ V|f(v)|, which is called the k-rainbow domination problem, is known to be NP-complete for arbitrary graphs and values of k. In this paper, we propose a dynamic programming algorithm to solve the k-rainbow domination problem for graphs with bounded tree-width tw in 𝒪((2k + 1+1)twn) time, where G has n vertices. Moreover, we also show that the same approach is applicable to solve the weighted k-rainbow domination problem with the same complexity. Therefore, both problems of k-rainbow and weighted k-rainbow domination belong to the class FPT, or fixed parameter tractable, with respect to tree-width. In addition to formally showing the correctness of our algorithms, we also implemented these algorithms to illustrate some examples.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.4
References
J. Alber, and R. Niedermeier, Improved tree decomposition based algorithms for dominationlike problems, Theoretical Informatics, Springer, (2002) 613–627.
S. Arnborg, D.G. Corneil, and A. Proskurowski, Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic Discrete Methods 8 (2) (1987), 277–284.
H.L. Bodlaender, A tourist guide through treewidth, Acta cybernetica 11 (1-2) (1993), 1–21.
H.L. Bodlaender, P. Bonsma, and D. Lokshtanov, The fine details of fast dynamic programming over tree decompositions, In: International Symposium on Parameterized and Exact
Computation, Springer (2013), 41–53.
H.L. Bodlaender, F.V. Fomin, A.M.C.A. Koster, D. Kratsch, and D.M. Thilikos (2006) On Exact Algorithms for Treewidth, In: Azar Y., Erlebach T. (eds) Algorithms – ESA 2006. Lecture Notes in Computer Science, Vol 4168, Springer.
H.L. Bodlaender, F.V. Fomin, A.M. Koster, D. Kratsch, and D.M. Thilikos, On exact algorithms for treewidth, ACM Transactions on Algorithms 9 (1) 12 (2012).
B. Bresar, M.A. Henning, and D.F. Rall, Paired-domination of Cartesian products of graphs and rainbow domination, Electronic Notes in Discrete Mathematics 22 (2005), 233–237.
B. Bresar, M.A. Henning, and D.F. Rall, Rainbow domination in graphs, Taiwanese Journal of Mathematics 12 (1) (2008), 213–225.
B. Bresar and T.K. Sumenjak, On the 2-rainbow domination in graphs, Discrete Appl. Math. 155 (17) (2007), 2394–2400.
G.J. Chang, B.J. Li, and J. Wu, Rainbow domination and related problems on strongly chordal graphs, Discrete Appl. Math. 161 (10) (2013), 1395–1401.
G.J. Chang, J. Wu, and X. Zhu, Rainbow domination on trees, Discrete Appl. Math. 158 (1) (2010), 8–12.
B. Courcelle, The expression of graph properties and graph transformations in monadic second-order logic, Handbook of Graph Grammars 1 (1997), 313–400.
L.R. Fuentes, I.J. Dejter, and C.A. Araujo, Rainbow perfect domination in lattice graphs, Electronic J. Graph Theory Appl. 6 (1) (2018), 95–112.
S. Fujita and M. Furuya: Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (6) (2013), 806–812.
W.K. Hon, T. Kloks, H.H. Liu, and H.L. Wang, Rainbow domination and related problems on some classes of perfect graphs, Springer International Publishing, Cham (2016), 121–134.
N.J. Rad and E. Shabani, On the complexity of some hop domination parameters, Electronic J. Graph Theory Appl. 7 (1), (2019), 77–89.
N. Robertson and P.D. Seymour, Graph minors. I. Excluding a forest. J. Combin. Theory Ser. B 35 (1) (1983), 39–61.
N. Robertson and P.D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, Journal of Algorithms 7 (3) (1986), 309–322.
T.K. Sumenjak, D.F. Rall, and A. Tepeh, Rainbow domination in the lexicographic product of graphs, Discrete Appl. Math. 161 (13) (2013), 2133–2141.
C. Tong, X. Lin, Y. Yang, and M. Luo, 2-rainbow domination of generalized Petersen graphs p(n, 2), Discrete Appl. Math. 157 (8) (2009), 1932–1937.
J.M. Van Rooij and H.L. Bodlaender, Exact algorithms for dominating set, Discrete Appl. Math. 159 (17) (2011), 2147–2164.
Y. Wang and K. Wu, A tight upper bound for 2-rainbow domination in generalized Petersen graphs, Discrete Appl. Math. 161 (13) (2013), 2178–2188.
G.J. Woeginger, Exact algorithms for NP-hard problems: A survey, In: Combinatorial Optimization—Eureka, You Shrink!, Springer (2003), 185–207.
Y. Wu and H. Xing, Note on 2-rainbow domination and Roman domination in graphs. Appl. Math. Lett. 23 (6) (2010), 706–709.
G. Xu, 2-rainbow domination in generalized Petersen graphs p(n, 3), Discrete Appl. Math. 157 (11) (2009), 2570 – 2573.
C.K. Yen, 2-rainbow domination and its practical variation on weighted graphs. In: Advances in Intelligent Systems and Applications-Volume 1, Springer (2013), 59–68.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.