The complexity of recognizing minimally tough graphs
Gyula Y. Katona, István Kovács, Kitti Varga · Discrete Applied Mathematics · 2021
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.