NP-completeness of k-Inversion for every positive k
Statement
For a tournament and a positive integer , the problem -Inversion asks whether can be made acyclic using at most, or equivalently in the paper's formulation exactly, inversions; the source states the resulting complexity claim in terms of NP-completeness.
Universal k-Inversion complexity conjecture.
The paper notes that this would follow from the dijoin additivity conjecture together with its proof that -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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.