MO417 - Questão para a prova oral

Número: 2013-104

Enunciado: Sabemos que o problema de decisão CLIQUE é NP-Completo. Analise as sentenças a seguir e identifique a alternativa correta.

I) O problema de decisão CLIQUE em grafos bipartidos está em P
II) O problema de decisão do CLIQUE em grafos planares está em P
III) O problema de decisão do CLIQUE em grafos densos, isto é, grafos onde o número de arestas é pelo menos 1/6 do quadrado do número de vértices, é NP-Completo

1. Apenas I está correta
2. Apenas II está correta
3. Apenas III está correta
4. Todas estão corretas
5. NDA

Ideia original de: John Edgar Vargas Muñoz