A note on the approximability of the tenacity of graphs

Abstract

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