A new approach on locally checkable problems
BONOMO-BRABERMAN, FLAVIA; GONZALEZ, CAROLINA LUCÍA
DISCRETE APPLIED MATHEMATICS
ELSEVIER SCIENCE BV
Lugar: Amsterdam; Año: 2022 vol. 314 p. 53 - 80
By providing a new framework, we extend previous results on locally checkable problems in boundedtreewidth graphs. As a consequence, we show how to solve, in polynomial time for bounded treewidthgraphs, [k]-Roman domination and Grundy domination, among other problems for which no suchalgorithm was previously known. Moreover, by proving that fixed powers of bounded degree andbounded treewidth graphs are also bounded degree and bounded treewidth graphs, we can enlarge thefamily of problems that can be solved in polynomial time for these graph classes, including distancecoloring problems and distance domination problems (for bounded distances).