A note on the approximability of the tenacity of graphs
Vahid Heidari, Dara Moazzami · International Symposium on Algorithms and Computation · 2020
In this paper we show that, if $NPneq ZPP$, for any $epsilon > 0$, the tenacity of graphwith $n$ vertices is not approximable in polynomial time within a factor of$frac{1}{2} left( frac{n-1}{2} right) ^{1-epsilon}$.