











Title 


Speaker 
이의웅 


Date 
20170706 


Host 



Place 
KAIST 




Abstract : Approximation algorithms and fixedparameter tractable (FPT) algorithms have been two major ways to deal with NPhardness of combinatorial optimization problems. The notion of FPT approximation can be naturally defined, and it is getting significant attention recently. Starting from gentle introductions to approximation algorithms and FPT algorithms, I will talk about my three recent results on FPT approximability.
– Given a graph G = (V, E) and an integer k, we study kApproximation algorithms and fixedparameter tractable (FPT) algorithms have been two major ways to deal with NPhardness of combinatorial optimization problems. The notion of FPT approximation can be naturally defined, and it is getting significant attention recently. Starting from gentle introductions to approximation algorithms and FPT algorithms, I will talk about my three recent results on FPT approximability.
– Given a graph G = (V, E) and an integer k, we study kVertex Separator, where the goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most k vertices. We give an O(log k)FPT approximation algorithm for kVertex Separator. Our result improves the best previous graph partitioning algorithms.
– We also study kPath Transversal, where the goal is to remove the minimum number of vertices such that there is no simple path of length k. We present an O(log k)FPT approximation algorithm for kPath Transversal. There was no nontrivial approximation algorithm for k > 4 before this work.
– Finally, kcut is the problem where we want to remove the minimum number of edges such that the graph has at least k connected components. We give a (2 – ε)FPT approximation algorithm for some epsilon > 0, improving upon a (nonFPT) 2approximation.
The third result is joint work with Anupam Gupta and Jason Li 





