On the small cycle transversal of planar graphs

AbstractWe consider the problem of finding a k-edge transversal set that intersects all (simple) cycles of length at most s in a planar graph, where s≥3 is a constant. This problem, referred to as Small Cycle Transversal, is known to be NP-complete. We present a polynomial–time algorithm that computes a kernel of size 36s3k for Small Cycle Transversal. In order to achieve this kernel, we extend the region decomposition technique of Alber et al. (2004) [1] by considering a unique region decomposition that is defined by shortest paths. Our kernel size is a significant improvement in terms of s over the kernel size obtained under the meta-kernelization framework by Bodlaender et al. (2009) [7]