MO417 - Questão para a prova oral

Número: 2009-168

Enunciado: Dadas as linguagens abaixo:

I - {<G,v,k> | G é um grafo orientado, v é um vértice de G e existe um caminho mínimo em G com pelo menos k arestas partindo de v}
II - {<G,k> | G é um grafo orientado e existe um caminho em G com pelo menos k arestas}
III - {<G> | G é um grafo orientado conexo e existe uma tour de Euler em G}
IV - {<G> | G é um grafo orientado com n vértices e existe um ciclo envolvendo no mínimo n-1 vértices de G}
V - {<F> | F é uma fórmula booleana em 2-CNF satisfatível}

Quais delas são NP-completas?

1. I, IV e V
2. II e IV
3. II e III
4. II, III e V
5. NDA

Ideia original de: José Vieira Maciel Borges