{"id":"arxiv/2602.11773","url":"https://arxiv.org/abs/2602.11773","tags":["cs.CC","math.CO"],"score":0,"title":"A Note on the Complexity of Directed Clique","domain":"cs.CC","source":"arxiv","authors":["Grzegorz Gutowski","Mikołaj Rams"],"reviews":0,"subject":"cs.CC","summary":"For a directed graph $G$, and a linear order $\\ll$ on the vertices of $G$, we define backedge graph $G^\\ll$ to be the undirected graph on the same vertex set with edge $\\{u,w\\}$ in $G^\\ll$ if and only if $(u,w)$ is an arc in $G$ and $w \\ll 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^\\ll$ taken over all linear orders $\\ll$ 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-12","reactions":{}}