Given once, 2012
Kernels for F-Deletion
Polynomial kernels for deleting a few vertices so that no forbidden minor remains
An advanced thesis defence, for researchers and faculty.
Abstract
Draft, not yet checked by meHow close is a graph to being acyclic, or planar, or of small treewidth? Many such properties are captured by forbidden minors, which leads to F-Deletion: delete at most k vertices so that no graph from a fixed family F remains as a minor. A conjecture says that F-Deletion has polynomial kernels exactly when F contains a planar graph. In my thesis defence I gather evidence for it: an approximation algorithm, polynomial kernels on claw-free graphs and whenever F contains θc (two vertices joined by c parallel edges), an Erdős–Pósa property for θc, and the protrusion-based reductions behind them. I also cover Independent Feedback Vertex Set and Colorful Motifs.
The slides
The viewer needs JavaScript; the PDF below works without it.