Space-Efficient Graph Kernelizations

Let n be the size of a parameterized problem and k the parameter. We present kernels for Feedback Vertex Set and Path Contraction whose sizes are all polynomial in k and that are computable in polynomial time and with \(O({{\,\textrm{poly}\,}}(k) \log n)\) bits (of working memory). By using kernel cascades, we obtain the best known kernels in polynomial time with \(O({{\,\textrm{poly}\,}}(k) \log n)\) bits.