Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00279
Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
Vol. 16, no. 4, pp. 811846, 2012. Regular paper.
Abstract In this paper we consider a natural generalization of the wellknown 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 polynomialtime factor O(n^{1/2 − ε}) or O( OPT^{1/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

Journal Supporters
