Bang-Jensen et al.'s NP-completeness conjecture for bounded inversion number
Statement
For a digraph , let be its inversion number, and let be a fixed positive integer.
Bang-Jensen et al.'s complexity conjecture. Deciding whether a given digraph has inversion number at most is NP-complete for any fixed positive integer .
The paper notes that the case is already known to be NP-complete and that the dijoin conjecture would imply the asserted result for every fixed . The source does not state a resolution.
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.