Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.11773 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908829521805312 |
|---|---|
| author | Gutowski, Grzegorz Rams, Mikołaj |
| author_facet | Gutowski, Grzegorz Rams, Mikołaj |
| contents | 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_11773 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Note on the Complexity of Directed Clique Gutowski, Grzegorz Rams, Mikołaj Computational Complexity Combinatorics 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 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 |
| topic | Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2602.11773 |