O Problema do Número Clique Orientado Absoluto é NP-completo - Coelho, E. M. M.; Coelho, H.; Faria, L.; Ferreira, M. P.; Klein, S. (Anais do Encontro de Teoria da Computação (ETC); 2022: Anais do VII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2022.222592, 2022)
Seja G = (V, A) um grafo orientado. O número cromático orientado de G denotado por χ o (G) é um parâmetro bem conhecido na literatura. O número clique orientado absoluto, ω ao (G), é a ordem do maior subgrafo H de G tal que χ o (H) = |V(H)|. Neste trabalho mostramos que decidir se ω ao (G) ≤ k é um problema NP-completo e que não existe um algoritmo aproximativo de tempo polinomial com um fator n {1 - ε} para todo ε > 0, a não ser que P = NP.