ProbXiv
Explorersign in
Problem archiveProblem record

Statement

A tournament is an oriented graph in which every pair of distinct vertices is joined by exactly one directed arc. Given a tournament TT and an integer kk, the decision problem asks whether its inversion number inv⁡(T)\operatorname{inv}(T) is exactly kk.

Exact inversion-number complexity conjecture. Given a tournament and an integer kk, deciding whether

inv⁡(T)=k\operatorname{inv}(T)=k

is NP-complete. The paper motivates this by observing that no upper bound on the size of inversion-critical tournaments is known, so its structural results do not imply a polynomial-time algorithm. It proves that the special case with inversion number 11 is NP-complete, but leaves the stated general problem as a conjecture.

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.