Lossy Kernels for Graph Contraction Problems

VCLA hosting a talk by Prafullkumar Tale

ABSTRACT

The focus of the vast majority of papers on parameterized graph editing problems, has so far been limited to edit operations that delete vertices, delete edges or add edges. In recent years, a different edit operation has begun to attract significant scientific attention. This operation, which is arguably the most natural edit operation apart from deletions/insertions of vertices/edges, is the one that contracts an edge. In this talk, we will talk about F-Contraction problem where the objective is to contract k edges in input graph so that the resulting graph belongs to F. It is known that Chordal Contraction, Split Contraction and Clique Contraction are W[2]-Hard, W[1]-Hard, and does not admit polynomial kernel, respectively. Inspired by the intractability results we study them from the viewpoint of parameterized approximation and lossy kernelization.

Prafullkumar Tale, Institute of Mathematical Sciences