ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

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.