DP-completeness of recognizing minimally t-tough graphs
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.