INAPPROXIMABILITY OF H-TRANSVERSAL/PACKING.

Given an undirected graph G = (VG,EG) and a fixed "pattern" graph H = (VH,EH) with k vertices, we consider the H-Transversal and H-Packing problems. The former asks to find the smallest S ⊆ VG such that the subgraph induced by VG \ S does not have H as a subgraph, and the latter asks to find the maximum number of pairwise disjoint k-subsets S1,...,Sm ⊆ VG such that the subgraph induced by each Si has H as a subgraph. We prove that if H is 2-connected, H-Transversal and H-Packing are almost as hard to approximate as general k-Hypergraph Vertex Cover and k-Set Packing, so it is NP-hard to approximate them within a factor of Ω(k) and Ω(k), respectively. We also show that there is a 1-connected H where H-Transversal admits an O(log k)-approximation algorithm, so that the connectivity requirement cannot be relaxed from 2 to 1. For a special case of H-Transversal where H is a (family of) cycles, we mention the implication of our result to the related Feedback Vertex Set problem and give a different hardness proof for directed graphs. [ABSTRACT FROM AUTHOR]