Strong Hardness of Approximation for Tree Transversals

12/03/2021
by   Euiwoong Lee, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset

Sign in with Google

×

Use your Google Account to sign in to DeepAI

×

Consider DeepAI Pro