TournamentClique completeness conjecture for the second level of the polynomial hierarchy
TournamentClique completeness conjecture for the second level of the polynomial hierarchy
A tournament is a directed graph in which exactly one of the two possible directions is chosen for every pair of distinct vertices. For a tournament , its directed clique number is the minimum, over all linear orders on , of the clique number of the corresponding backedge graph . The problem TournamentClique asks, given a tournament and a positive integer , whether . The class is the second level of the polynomial hierarchy. TournamentClique completeness conjecture. TournamentClique is -complete. This would settle the complexity of TournamentClique, which is already known to lie in ; the conjectured hardness remains open.
Sources & referencesView supporting material
Primary source
Grzegorz Gutowski and Mikołaj Rams, “A Note on the Complexity of Directed Clique”, arXiv:2602.11773 (2026).
Progress summary
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.