Kernels for the F-Deletion Problem

The thesis is largely concerned with the Planar F-deletion problem, which seeks the smallest number of vertices that we must delete from a graph G to ensure that it contains no minor models of graphs from F (F is a family of connected graphs containing at least one planar graph). The thesis explores the kernelization complexity and explores some closely related structural questions. En route, we devise an approximation algorithm for the problem which can be useful in other contexts. An interesting variety of techniques are called upon as we journey through variants of the general question, ranging from applications of Courcelle’s theorem to using protrusion-based techniques.

Remark: There has been substantial progress in this line of work since the writing of the thesis. In particular, the question of whether Planar F-deletion admits a polynomial kernel is fully resolved and the answer is affirmative. The most recent work makes no assumption about the connectivity of the graphs in F.

Advisors: Prof. Venkatesh Raman and Prof. Saket Saurabh

View Abstract