University of TehranJournal of Algorithms and Computation2476-277652220201201A note on the approximability of the tenacity of graphs1491577927010.22059/jac.2020.79270ENVahid HeidariUniversity of Tehran, Department of Algorithms and Computation.Dara MoazzamiUniversity of Tehran, College of Engineering, Faculty of Engineering ScienceJournal Article20210101In this paper we show that, if $NP\neq ZPP$, for any $\epsilon > 0$, the tenacity of graph<br />with $n$ vertices is not approximable in polynomial time within a factor of<br />$\frac{1}{2} \left( \frac{n-1}{2} \right) ^{1-\epsilon}$.https://jac.ut.ac.ir/article_79270_0a4d1e9aa72c099beb4fcfe521d1bc23.pdf