The 2-DIOMEGA-ORDERING NP-completeness conjecture

Let TT be a tournament, and let ω(T)\operatorname{\overrightarrow{\omega}}(T) denote the minimum, over all orderings of V(T)V(T), of the clique number of the corresponding backedge graph. The 2-DIOMEGA-ORDERING conjecture. The problem of deciding whether ω(T)2\operatorname{\overrightarrow{\omega}}(T)\leq 2 is NP-complete. The cases k=1k=1 and k3k\geq 3 are respectively polynomial and NP-complete; the source presents the case k=2k=2 as the remaining question, but does not provide a resolution.

Sources & referencesView supporting material

Primary source

Guillaume Aubian, “Computing the clique number of tournaments”, arXiv:2401.07776 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.