Turing kernelization for finding long paths and cycles in restricted graph classes

Abstract. We analyze the potential for provably effective preprocessing for the problems of finding paths and cycles with at least k edges. Several years ago, the question was raised whether the existing superpolynomial kernelization lower bounds for k-Path and k-Cycle can be circumvented by relaxing the requirement that the preprocessing algorithm outputs a single instance. To this date, very few examples are known where the relaxation to Turing kernelization is fruitful. We provide a novel example by giving polynomial-size Turing kernels for k-Path and k-Cycle on planar graphs, graphs of maximum degree t, claw-free graphs, and K3,t-minor-free graphs, for each constant t ≥ 3. Concretely, we present algorithms for k-Path (k-Cycle) on these restricted graph families that run in polynomial time when they are allowed to query an external oracle for the answers to k-Path (k-Cycle) instances of size and parameter bounded polynomially in k. Our kernelization schemes are based on a new methodology called Decompose-Query-Reduce.