DP-completeness of recognizing minimally -tough graphs
DP-completeness of recognizing minimally -tough graphs
Let be a positive rational number. The decision problem -Tough asks whether a graph is minimally -tough, meaning that its toughness is at least and deleting any edge decreases its toughness below .
Min--Tough complexity conjecture. -Tough is DP-complete for any positive rational number .
The paper proves DP-completeness for some positive rational values of , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.