The Taub Faculty of Computer Science Events and Talks

The concept of a graph minor is fundamental in topological graph theory. First, I will describe the cornerstones of this theory from the lens of parameterized complexity. Next, I will survey more recent results concerning minor-hitting problems, focusing on three algorithmic paradigms: approximation, kernelization, and parameterized algorithms. Here, an important special case is the Vertex Planarization problem (remove as few vertices as possible to make a given graph planar) – this problem is equivalent to hitting all K_5 and K_{3,3} minors in a given graph. Finally, I will talk about our recent result: an O(1)-approximate kernel for Vertex Planarization, being a combination of approximation and kernelization. This is a joint work with Bart. M. P. Jansen. No prior background on graph minors or kernelization is required.