Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights

Abstract

In this paper we consider a natural generalization of the well-known MAX LEAF SPANNING TREE problem. In the generalized WEIGHTED MAX LEAF problem we get as input an undirected connected graph G, a rational number k not smaller than 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 polynomial time into an equivalent instance 〈G′,w′,k′〉 such that |V(G′)| ≤ 5.5k and k′ ≤ k. In the context of parameterized 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 = (V,E) that excludes some simple substructures always contains a spanning tree with at least |V|/5.5 leaves. We also prove that WEIGHTED MAX LEAF does not admit a polynomial-time factor O(n^{1/2 − ε}) or O( OPT^{1/3 − ε}) approximation algorithm for any ε > 0 unless P=NP.