In this paper we show that, if $NP\neq ZPP$, for any $\epsilon > 0$, the tenacity of graph with $n$ vertices is not approximable in polynomial time within a factor of $\frac{1}{2} \left( \frac{n-1}{2} \right) ^{1-\epsilon}$.
Heidari, V., & Moazzami, D. (2020). A note on the approximability of the tenacity of graphs. Journal of Algorithms and Computation, 52(2), 149-157. doi: 10.22059/jac.2020.79270
MLA
Vahid Heidari; Dara Moazzami. "A note on the approximability of the tenacity of graphs". Journal of Algorithms and Computation, 52, 2, 2020, 149-157. doi: 10.22059/jac.2020.79270
HARVARD
Heidari, V., Moazzami, D. (2020). 'A note on the approximability of the tenacity of graphs', Journal of Algorithms and Computation, 52(2), pp. 149-157. doi: 10.22059/jac.2020.79270
VANCOUVER
Heidari, V., Moazzami, D. A note on the approximability of the tenacity of graphs. Journal of Algorithms and Computation, 2020; 52(2): 149-157. doi: 10.22059/jac.2020.79270
)