






홈 > 학술정보 >학술행사 > 세미나 





KAIST Discrete Math 세미나 



FPT Approximation Algorithms for Graph Problems 

이의웅 (Computer Science Department, Carnegie Mellon University ) 
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 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. 







