  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. A graph is minimally
$t$-tough if the toughness of the graph is $t$ and the deletion of any edge
from the graph decreases the toughness. The complexity class DP is the set of
all languages that can be expressed as the intersection of a language in NP and
a language in coNP. In this paper, we prove that recognizing minimally
$t$-tough graphs is DP-complete for any positive rational number $t$. We
introduce a new notion called weighted toughness, which has a key role in our
proof.
