Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights

In this paper we consider a natural generalization of the wellknownMaxLeafSpanningTreeproblem. In the generalizedWeighted Max Leaf problem we get as input an undirected connected graph G = (V, E), a rational number k ≥ 1 and a weight function w : V → Q≥1 on the vertices, and are asked whether a spanning tree T for G exists such that the combined weight of the leaves of T is at least k. We show that it is possible to transform an instance 〈G, w, k〉 of Weighted Max Leaf in linear time into an equivalent instance 〈G′, w′, k′〉 such that |V ′| ≤ 5.5k′ and k′ ≤ k. In the context of fixed parameter complexity this means that Weighted Max Leaf admits a kernel with 5.5k vertices. The analysis of the kernel size is based on a new extremal result which shows that every graph G that excludes some simple substructures always contains a spanning tree with at least |V |/5.5 leaves.