O Problema do Número Clique Orientado Absoluto é NP-completo
Resumo
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.
Palavras-chave:
Grafo Orientado, Número Clique Orientado, Número Cromático Orientado
Referências
Courcelle, B. (1994). The monadic second order logic of graphs VI: On several representations of graphs by relational structures. Discrete Applied Mathematics, 54(2-3):117–149.
Das, S., Prabhu, S., e Sen, S. (2018). A study on oriented relative clique number. Discrete Mathematics, 341(7):2049–2057.
Garey, M. R. e Johnson, D. S. (1979). Computers and Intractability, volume 174. Freeman San Francisco.
Klostermeyer, W. e MacGillivray, G. (2004). Analogues of cliques for oriented coloring. Discussiones Mathematicae Graph Theory, 24(3):373–387.
Raspaud, A. e Sopena, E. (1994). Good and semi-strong colorings of oriented planar graphs. Information Processing Letters, 51(4):171–174.
Sopena, É. (2016). Homomorphisms and colourings of oriented graphs: An updated survey. Discret. Math., 339(7):1993–2005.
Zuckerman, D. (2006). Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 681–690.
Das, S., Prabhu, S., e Sen, S. (2018). A study on oriented relative clique number. Discrete Mathematics, 341(7):2049–2057.
Garey, M. R. e Johnson, D. S. (1979). Computers and Intractability, volume 174. Freeman San Francisco.
Klostermeyer, W. e MacGillivray, G. (2004). Analogues of cliques for oriented coloring. Discussiones Mathematicae Graph Theory, 24(3):373–387.
Raspaud, A. e Sopena, E. (1994). Good and semi-strong colorings of oriented planar graphs. Information Processing Letters, 51(4):171–174.
Sopena, É. (2016). Homomorphisms and colourings of oriented graphs: An updated survey. Discret. Math., 339(7):1993–2005.
Zuckerman, D. (2006). Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 681–690.
Publicado
31/07/2022
Como Citar
COELHO, E. M. M.; COELHO, H.; FARIA, L.; FERREIRA, M. P.; KLEIN, S..
O Problema do Número Clique Orientado Absoluto é NP-completo. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 13-16.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.222592.
