Kernelization for cycle transversal problems

We present new kernelization results for two problems, ss-cycle transversal and (≤s)(≤s)-cycle transversal, when ss is 4 or 5. We show that 4-cycle transversal and ≤4≤4-cycle transversal admit 6k26k2 vertex kernels in general graphs. We then prove NP-completeness of ss-cycle transversal and (≤s)(≤s)-cycle transversal in planar graphs for s>3s>3. We show the following linear vertex kernels in planar graphs—a 74k74k vertex kernel for 4-cycle transversal; a 32k32k vertex kernel for (≤4)(≤4)-cycle transversal; a 266k266k vertex kernel for (≤5)(≤5)-cycle transversal.