Document Type : Research Paper

Authors

• Vahid Heidari ¹
• Dara Moazzami ²

¹ University of Tehran, Department of Algorithms and Computation.

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

Abstract

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

Keywords

• $NP$-complete problem
• tenacity
• tenacious
• $NP$-hard