Inapproximability of $H$-Transversal/Packing

Abstract

Given an undirected graph $G=(V_G,E_G)$ and a fixed "pattern" graph $H=(V_H,E_H)$ with $k$ vertices, we consider the $H$-Transversal and $H$-Packing problems. The former asks to find the smallest $S\subseteq V_G$ such that the subgraph induced by $V_G\setminus S$ does not have $H$ as a subgraph, and the latter asks to find the maximum number of pairwise disjoint $k$-subsets $S_1,...,S_m\subseteq V_G$ such that the subgraph induced by each $S_i$ 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 $\Omega (k)$ and $\tilde{\Omega }(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.

31 pages, 2 figures