Safe set is NP-complete for strong tournaments
Statement
A tournament is a digraph obtained by orienting every edge of a complete graph, and a tournament is strong if it is strongly connected. A safe set is a vertex set satisfying the safe-set condition, and the associated decision problem asks whether a safe set of a prescribed size exists.
Strong-tournament safe-set conjecture. The safe-set problem is NP-complete for strong tournaments.
This conjecture extends the paper's NP-completeness result for tournaments. The supplied text explains that the existing proof uses a tournament that is not strongly connected and therefore does not establish this stronger claim; its status is consequently open.
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.