2026-07-21T03:09:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26188 2026-07-02T07:14:09Z ddc:004 open_access

A Note on the Complexity of Directed Clique Gutowski, Grzegorz Rams, Mikołaj Directed Clique Computational Complexity Polynomial Hierarchy For a directed graph G, and a linear order ≪ on the vertices of G, we define the backedge graph G^≪ to be the undirected graph on the same vertex set with edge {u,w} in G^≪ if and only if (u,w) is an arc in G and w ≪ u. The directed clique number of a directed graph G is defined as the minimum size of the maximum clique in the backedge graph G^≪ taken over all linear orders ≪ on the vertices of G. A natural computational problem is to decide for a given directed graph G and a positive integer t, if the directed clique number of G is at most t. This problem has polynomial algorithm for t = 1 and is known to be NP-complete for every fixed t ≥ 3, even for tournaments. In this note we prove that this problem is Σ^𝖯₂-complete when t is given on the input. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Grzegorz Gutowski and Mikołaj Rams 2026 Is Part Of LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WG.2026.22 urn:nbn:de:0030-drops-261885 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.22 eng https://creativecommons.org/licenses/by/4.0/legalcode