# Kernel bounds for disjoint cycles and disjoint paths

3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this paper, we show that the problems Disjoint Cycles and Disjoint Paths do not have polynomial kernels, unless N P ‚äÜ c o N P / p o l y . Thus, these problems do not allow polynomial time preprocessing that results in instances whose size is bounded by a polynomial in the parameter at hand. We build upon recent results by Bodlaender et¬†al. [6] and Fortnow and Santhanam [20], that show that NP-complete problems that are ‚Äòor-compositional‚Äô do not have polynomial kernels, unless N P ‚äÜ c o N P / p o l y . To this machinery, we add a notion of transformation, and obtain that Disjoint Cycles, and Disjoint Paths do not have polynomial kernels, unless N P ‚äÜ c o N P / p o l y . For the proof, we introduce a problem on strings, called Disjoint Factors, and first show that this problem has no polynomial kernel unless N P ‚äÜ c o N P / p o l y . We also show that the related Disjoint Cycles Packing problem has a kernel of size O ( k log k ) .
Keywords :
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2011, 412, pp.4570-4578. 〈10.1016/j.tcs.2011.04.039〉

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00806805
Contributeur : Alexandre Pinlou <>
Soumis le : mardi 2 avril 2013 - 13:47:19
Dernière modification le : mardi 17 avril 2018 - 11:48:04

### Citation

Hans L. Bodlaender, Stéphan Thomassé, Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theoretical Computer Science, Elsevier, 2011, 412, pp.4570-4578. 〈10.1016/j.tcs.2011.04.039〉. 〈lirmm-00806805〉

### Métriques

Consultations de la notice