Can I read Strong Hardness of Approximation for Tree Transversals on EtoBox?

Strong Hardness of Approximation for Tree Transversals by Euiwoong Lee; Pengxiang Wang is a Computer Science article available to read on EtoBox.

What is Strong Hardness of Approximation for Tree Transversals about?

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 strongest known 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.

Who reads Strong Hardness of Approximation for Tree Transversals?

Author

Euiwoong Lee; Pengxiang Wang

Publisher

Elsevier BV

Published

2023

Language

EN

Field

Computer Science (Physical Sciences)