DP-completeness of recognizing minimally tt-tough graphs

Let tt be a positive rational number. The decision problem \scshapeMint{\scshape Min-}t-Tough asks whether a graph is minimally tt-tough, meaning that its toughness is at least tt and deleting any edge decreases its toughness below tt.

Min-tt-Tough complexity conjecture. \scshapeMint{\scshape Min-}t-Tough is DP-complete for any positive rational number tt.

The paper proves DP-completeness for some positive rational values of tt, while the remaining values are stated to be open; thus the assertion is unresolved in the full stated range.

Sources & referencesView supporting material

Primary source

Gyula Y Katona, István Kovács and Kitti Varga, “The complexity of recognizing minimally tough graphs”, arXiv:1705.10570 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.