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.
