%0 Journal Article
%T Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes
%A Bart M. P. Jansen
%J Computer Science
%D 2014
%I arXiv
%X 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 K_{3,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.
%U http://arxiv.org/abs/1402.4718v1