A Kernel for Convex Recoloring of Weighted Forests

摘要

In this paper, we show that the following problem has a kernel of quadratic size: given is a tree T whose vertices have been assigned colors and a non-negative integer weight, and given is an integer k. In a recoloring, the color of some vertices is changed. We are looking for a recoloring such that each color class induces a subtree of T and such that the total weight of all recolored vertices is at most k. Our result generalizes a result by Bodlaender et al. [3] who give quadratic size kernel for the case that all vertices have unit weight.