BIU theory seminar - March 29 : Michal Wlodarczyk - Hitting Minors, Planarization, and Kernelization

[Arnold Filtser]

Hello all,

This week (Wed March 22) there is no theory seminar.

We will meet again for our theory seminar on March 29, at 12.

Location:  Building 605 room 14

See you there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Michal Wlodarczyk (BGU) 
Title: Hitting Minors, Planarization, and Kernelization  
Abstract: Abstract: 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.

[Arnold Filtser]

Reminder- The theory seminar will take place tomorrow at 12 as scheduled.

See you there!