Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes

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^{\mathrm{\prime }},k^{\mathrm{\prime }})$ of size polynomial in $k$ unless $NP \subseteq coNP/poly$\mathrm{.}Thesamepositiveandnegativeresultsapplytothe$k$-Cycleproblem,whichasksfortheexistenceofacycleoflengthatleast$k$. Our kernelization schemes are based on a new methodology called Decompose-Query-Reduce.