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

0166-218X

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).