Given a graph G = (V, E) and an integer k, we study k-Vertex 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. Our problems can be interpreted as a special case of three general classes of problems that have been studied separately (balanced graph partitioning, Hypergraph Vertex Cover (HVC), and fixed parameter tractability (FPT).Our main result is an O(log k)-approximation algorithm for k-Vertex Separator. Our result improves the best previous graph partitioning algorithms. We also study k-Path Transversal, where the goal is to remove the minimum number of vertices such that there is no simple path of length k. With additional ideas from FPT algorithms and graph theory, we present an O(log k)-approximation algorithm for k-Path Transversal.The talk will include a gentle introduction to approximation algorithms and linear programming.

Euiwoong Lee is a Ph.D. student at Carnegie Mellon University, advised by Venkatesan Guruswami. He received his B.S. (2009) and M.S (2012) degrees from California Institute of Technology. Euiwoong is broadly interested in the approximate solvability of optimization problems, and his work has touched upon central topics in constraint satisfaction, graph theory, coding theory, game theory, combinatorial optimization and the power of linear/semidefinite programs. He is a recipient of the Simons Award for Graduate Students in Theoretical Computer Science.