A note on the approximability of the toughness of graphs

We show that, if <f>NP≠ZPP</f>, for any <f>&epsiv;>0</f>, the toughness of a graph with <f>n</f> vertices is not approximable in polynomial time within a factor of <f><NU>1</NU>/2</fr><hsp sp="0.16">(n/2)1−&epsiv;</f>. We give a 4-approximation for graphs with toughness bounded by <f><fr style="s" shape="case" ALIGN="C"><NU>1</NU>/3 (n/2)1−&epsiv;</f>. We give a 4-approximation for graphs with toughness bounded by <f><NU>1</NU>/3</f> 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 <f>P=NP</f>. [Copyright &y& Elsevier]