Bang-Jensen et al.'s NP-completeness conjecture for bounded inversion number
Bang-Jensen et al.'s NP-completeness conjecture for bounded inversion number
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Guillaume Aubian, Frédéric Havet, Florian Hörsch, Felix Klingelhoefer, Nicolas Nisse, Clément Rambaud and Quentin Vermande, “Problems, proofs, and disproofs on the inversion number”, arXiv:2212.09188 (2022).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.