{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidja2tncx2d6o7aoiq4jlays3d2d2u5i6t2fi3bwhmszo2eeol7si",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mepo3gpznw52"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.11773v1",
  "publishedAt": "2026-02-13T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Grzegorz Gutowski",
    "Mikołaj Rams"
  ],
  "textContent": "**Authors:** Grzegorz Gutowski, Mikołaj Rams\n\nFor 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 problem has polynomial algorithm for $t=1$ and is known to be \\NP-complete for every fixed $t\\ge3$, even for tournaments. In this note we prove that this problem is $Σ^\\mathsf{P}_{2}$-complete when $t$ is given on the input.",
  "title": "A Note on the Complexity of Directed Clique"
}