The 20th KMGS will be held on May 18th, Thursday, at Natural Science Building (E6-1) Room 1501.
We invite a speaker Jungho Ahn from the Dept. of Mathematical Sciences, KAIST.
The abstract of the talk is as follows.
Slot (AM 11:50~PM 12:30)
[Speaker] 안정호 (Jungho Ahn) from Dept. of Mathematical Sciences, KAIST, supervised by Prof. 엄상일 교수님(Sang-il Oum)
[Title] Introduction to Kernelization
[Discipline] Graph Theory, Complexity Theory
[Abstract]
We introduce concepts of parameterized complexity, especially, kernelization. Kernelization is a polynomial-time preprocessing algorithm that converts a given instance for a problem to a smaller instance while keeping the answer to the problem. Delicate kernelization mostly boosts the speed of solving the problem. We explain standard techniques in kernelizations, for instance, the sunflower lemma. Most optimization problems can be reformulated in the Hitting Set problem format, and the sunflower lemma gives us a simple yet beautiful kernelization for the problem. We further introduce our recent work about the Hitting Set problem on sparse graph classes.
[Language] Korean but English if it is requested.