The absolute oriented clique number problem is NP-complete - Coelho, E. M. M.; Coelho, H.; Faria, L.; Ferreira, M. P.; Klein, S. (Proceedings of the Theory of Computation Meeting (ETC), 2022)
Let G = (V, A) be an oriented graph. The oriented chromatic number of G denoted by χ o (G) is a well-know parameter in the literature. The absolute oriented clique number, ω ao (G), is the order of the largest subgraph H of G such that χ o (H) = |V(H)|. In this work we show that deciding if ω ao (G) ≤ k is an NP-complete problem and there is no polynomial-time approximation within a factor of n {1 - ε} for all ε > 0, unless P = NP.