Approximation algorithms for hitting subgraphs
share
Let H be a fixed undirected graph on k vertices. The H-hitting set problem asks for deleting a minimum number of vertices from a given graph G in such a way that the resulting graph has no copies of H as a subgraph. This problem is a special case of the hypergraph vertex cover problem on k-uniform hypergraphs, and thus admits an efficient k-factor approximation algorithm. The purpose of this article is to investigate the question that for which graphs H this trivial approximation factor k can be improved.
READ FULL TEXT