Safe set is NP-complete for strong tournaments

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.