A note on the approximability of the tenacity of graphs

Document Type : Research Paper


1 University of Tehran, Department of Algorithms and Computation.

2 University of Tehran, College of Engineering, Faculty of Engineering Science


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}$.