Computer Science Speaker Skills Talk
— 1:00pm
Location:
ASA Conference Room 6115
-
Gates Hillman Centers
Speaker:
EUIWOONG LEE
,
Ph.D. Student
http://www.cs.cmu.edu/~euiwoonl/
Given a fixed graph H with k vertices, H-Transversal is the problem to remove the minimum number of vertices from a large graph G so that G does not have H as a subgraph. This problem captures many fundamental combinatorial optimization problems as special cases, especially when H is a clique, a cycle, or a path. We study how approximability of H-Transversal changes depending on H. A simple greedy algorithm achieves k-approximation whenever H has k vertices. We show that if H is 2-vertex-connected, we cannot have better than a (k-1)-approximation algorithm unless NP is contained in RP. We also prove that among 1-vertex-connected graphs, both k-Path Transversal and k-Star Transversal admit an O(log k)-approximation algorithm. The algorithm for k-Path Transversal reveals an interesting connection between H-Transversal and graph partitioning. Presented in Partial Fulfillment of the CSD Speaking Skills Requirement