  The NP-complete $k$-Path problem asks whether a given undirected graph has a
(simple) path of length at least $k$. We prove that $k$-Path has
polynomial-size Turing kernels when restricted to planar graphs, graphs of
bounded degree, claw-free graphs, or to $K_{3,t}$-minor-free graphs for some
constant $t$. This means that there is an algorithm that, given a $k$-Path
instance $(G,k)$ belonging to one of these graph classes, computes its answer
in polynomial time when given access to an oracle that solves $k$-Path
instances of size polynomial in $k$ in a single step. The difficulty of
$k$-Path can therefore be confined to subinstances whose size is independent of
the total input size, but is bounded by a polynomial in the parameter $k$
alone. These results contrast existing superpolynomial lower bounds for the
sizes of traditional kernels for the $k$-Path problem on these graph classes:
there is no polynomial-time algorithm that reduces any instance $(G,k)$ to a
single, equivalent instance $(G',k')$ of size polynomial in $k$ unless $NP
\subseteq coNP/poly$. The same positive and negative results apply to the
$k$-Cycle problem, which asks for the existence of a cycle of length at least
$k$. Our kernelization schemes are based on a new methodology called
Decompose-Query-Reduce.
