NP-completeness of exact tournament inversion number
Statement
A tournament is an oriented graph in which every pair of distinct vertices is joined by exactly one directed arc. Given a tournament and an integer , the decision problem asks whether its inversion number is exactly .
Exact inversion-number complexity conjecture. Given a tournament and an integer , deciding whether
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 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.