Looking at the stars
The problem of packing k vertex-disjoint copies of a graph H into another graph G is NP-complete if H has more than two vertices in some connected component. In the framework of parameterized complexity, we analyze a particular family of instances of this problem, namely the packing of stars. We give a quadratic kernel for packing k copies of H = K(1,s),,. When we consider the special case of s = 2, i.e. H being a star with two leaves, we give a linear kernel and an algorithm running in time sigma(2(5.30)vertical bar(k)k(2.5) + n(3)). (c) 2005 Elsevier B.V. All rights reserved.
fixed parameter algorithms crown reduction