Strong Hardness of Approximation for Tree Transversals
share
Let H be a fixed graph. The H-Transversal problem, given a graph G, asks to remove the smallest number of vertices from G so that G does not contain H as a subgraph. While a simple |V(H)|-approximation algorithm exists and is believed to be tight for every 2-vertex-connected H, the best hardness of approximation for any tree was Ω(log |V(H)|)-inapproximability when H is a star. In this paper, we identify a natural parameter Δ for every tree T and show that T-Transversal is NP-hard to approximate within a factor (Δ - 1 -ε) for an arbitrarily small constant ε > 0. As a corollary, we prove that there exists a tree T such that T-Transversal is NP-hard to approximate within a factor Ω(|V(T)|), exponentially improving the best known hardness of approximation for tree transversals.
READ FULL TEXT