Approximation Algorithms for H-Transversal
October 19, 2016

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.