The 2-DIOMEGA-ORDERING NP-completeness conjecture
The 2-DIOMEGA-ORDERING NP-completeness conjecture
Let be a tournament, and let denote the minimum, over all orderings of , of the clique number of the corresponding backedge graph. The 2-DIOMEGA-ORDERING conjecture. The problem of deciding whether is NP-complete. The cases and are respectively polynomial and NP-complete; the source presents the case 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
Sign in to submit a solution.
No solutions have been posted yet.