Bang-Jensen et al.'s NP-completeness conjecture for bounded inversion number

From papers

For a digraph DD, let inv(D)\operatorname{inv}(D) be its inversion number, and let kk be a fixed positive integer.

Bang-Jensen et al.'s complexity conjecture. Deciding whether a given digraph DD has inversion number at most kk is NP-complete for any fixed positive integer kk.

The paper notes that the case k=1k=1 is already known to be NP-complete and that the dijoin conjecture would imply the asserted result for every fixed kk. 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

No solutions have been posted yet.