ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For a tournament TT and a positive integer kk, the problem kk-Inversion asks whether TT can be made acyclic using at most, or equivalently in the paper's formulation exactly, kk inversions; the source states the resulting complexity claim in terms of NP-completeness.

Universal k-Inversion complexity conjecture.

k-Inversion is NP-complete for all positive integers k.\text{$k$-Inversion is NP-complete for all positive integers }k.

The paper notes that this would follow from the dijoin additivity conjecture together with its proof that 11-Inversion is NP-complete. Thus the assertion remains conditional on the unresolved dijoin 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.