Kernel bounds for disjoint cycles and disjoint paths - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Theoretical Computer Science Year : 2011

Kernel bounds for disjoint cycles and disjoint paths

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

Dates and versions

lirmm-00806805 , version 1 (02-04-2013)

Identifiers

Cite

Hans L. Bodlaender, Stéphan Thomassé, Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theoretical Computer Science, 2011, 412, pp.4570-4578. ⟨10.1016/j.tcs.2011.04.039⟩. ⟨lirmm-00806805⟩
2693 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More