Strengthening some complexity results on toughness of graphs
Let $t$ be a positive real number. A graph is called $t$ tough if the removal of any vertex set $S$ that disconnects the graph leaves at most |S|/t$ components. The toughness of a graph is the largest $t$ for which the graph is $t$ tough. The main results of this paper are the following. For any positive rational number $t \le 1$ and for any $k \ge 2$ and $r \ge 6$ integers recognizing $t$ tough bipartite graphs is coNP complete (the case $t=1$ was already known) and this problem remains coNP complete for $k$ connected bipartite graphs, and so does the problem of recognizing 1 tough r regular bipartite graphs. To prove these statements we also deal with other related complexity problems on toughness. In this paper we prove the following. For any positive rational number $t$ deciding whether \tau(G)=t$ is DP complete and if $t 1$ this problem remains DP complete for bipartite graphs. For any integer $k \ge 2$ and positive rational number $t \le 1$ recognizing $t$ tough $k$ connected bipartite graphs is coNP complete. For any integer $r \ge 5$ recognizing $1/2$ tough $r$ regular graphs is coNP complete. For any integer $r \ge 6$ recognizing 1 tough $r$ regular bipartite graphs is coNP complete. For any positive rational number $t 2/3$ we give a polynomial time algorithm for recognizing 3 regular graphs with toughness $t$ Finally, we prove that every connected 4 regular graph is 1/2 tough.
ArXiv