Publication at Faculty of Mathematics and Physics |
2022
Abstract
We study the graph burning problem and give a polynomial-time approximation scheme (PTAS) for arbitrary graphs of constant treewidth. This significantly extends the previous results, as a PTAS was known only for disjoint union of paths.
As a building block, we give an algorithm that proves the non-uniform k-center problem to be in XP when parameterized by the number of different radii and the treewidth of the graph. This extends the known exactly solvable cases of the non-uniform k-center problem; in particular this also solves the k-center with outliers on graphs of small treewidth exactly.