Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
Vol. 16, no. 4, pp. 811-846, 2012. Regular paper.
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: VQ ≥ 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(n1/2 − ε) or O( OPT1/3 − ε) approximation algorithm for any ε > 0 unless P=NP.
Submitted: September 2011.
Reviewed: May 2012.
Revised: July 2012.
Accepted: October 2012.
Final: October 2012.
Published: October 2012.
Communicated by Gerhard J. Woeginger
article (PDF)