A note on the approximability of the toughness of graphs

We show that, if NP not equal ZPP, for any epsilon > 0, the toughness of a graph with n vertices is not approximable in polynomial time within a factor of (1)/(2) (n/2)(1-epsilon). We give a 4-approximation for graphs with toughness bounded by (1)/(3) and we show that this result cannot be generalized to graphs with a bounded toughness. More exactly we prove that there is no constant approximation for graphs with bounded toughness, unless P = NP. (C) 2003 Elsevier B.V. All rights reserved.