کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435177 | 689877 | 2016 | 9 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 640, 9 August 2016, Pages 61–69