Strong Hardness of Approximation for Tree Transversals

Euiwoong Lee, Pengxiang Wang

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. Wh…