Computer Science Speaker Skills Talk

Wednesday, April 19, 2017 - 12:00pm to 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

For More Information, Contact:

deb@cs.cmu.edu

Keywords:

Speaking Skills