Edge-disjoint packing of stars and cycles

We study the parameterized complexity of two graph packing problems, Edge-Disjointk-Packing ofs-Stars and Edge-Disjointk-Packing ofs-Cycles. With respect to the choice of parameters, we show that although the two problems are FPT with both k and s as parameters, they are unlikely to be fixed-parameter tractable when parameterized by only k or only s. In terms of kernelization complexity, we show that Edge-Disjointk-Packing ofs-Stars has a kernel with size polynomial in both k and s, but in contrast, unless NP ⊆ coNP/poly, Edge-Disjointk-Packing ofs-Cycles does not have a kernel with size polynomial in both k and s, and moreover does not have a kernel with size polynomial in s for any fixed k. We also show that Edge-Disjointk-Packing of 4-Cycles admits a 96k296k2 kernel in general graphs and a 96k kernel in planar graphs.