ProbXiv
Explorersign in
Problem archiveProblem record

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.