Lossy Kernels for Few Graph Contraction ProbleMS

Abstract

We study a few graph contraction problems Chordal Contraction, Clique Contraction and Split Contraction, from the viewpoint of Lossy Kernelization, which is a recently introduced framework to study NP-hard problems. H-Contraction problem is to find set of edges such that when contracted will give the graph H. We study approximate kernel for the minimization version of these problems by including some parameters.