Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Hitting Minors, Planarization, and Kernelization
event speaker icon
Michal Wlodarczyk (Ben-Gurion University)
event date icon
Wednesday, 25.01.2023, 12:30
event location icon
Taub 201
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.