Problema de clique

O problema do clique ( notado com CLIQUE ) é um problema de decisão na teoria dos grafos . O problema do clique é um dos 21 problemas NP-completos clássicos , que Richard M. Karp provou em 1972 pertencer a essa classe .

Problema

A questão é se existe um clique de tamanho mínimo n em G para um grafo simples G e um número n ; isto é, se G tem pelo menos n nós que estão todos conectados aos pares.

frase

CLIQUE é NP-completo .

Ideia de prova

Redução do tempo polinomial de 3KNF-SAT para CLIQUE:

{\ displaystyle {3KNF-SAT} \ preceq _ {p} CLIQUE}

Visto que 3KNF-SAT é NP-difícil , isso também se aplica a CLIQUE. Além disso, pode ser facilmente mostrado que o próprio CLIQUE está em NP, portanto, no geral, é NP-completo.

Esboço de evidência

Seja F uma fórmula com n cláusulas em 3KNF, ou seja, na forma normal conjuntiva com no máximo três literais por cláusula:

{\ displaystyle F = (y_ {1,1} \ lor \ dotsc \ lor y_ {1, a_ {1}}) \ land \ dotsc \ land (y_ {n, 1} \ lor \ dotsc \ lor y_ {n , em}})}

{\ displaystyle {\ text {with}} \ \ forall _ {1 \ leq i \ leq n}: 1 \ leq a_ {i} \ leq 3}

{\ displaystyle {\ text {and}} \ \ \ forall _ {i, j}: y_ {i, j} \ in \ {x_ {1}, ..., x_ {m}, {\ overline {x_ {1}}}, ..., {\ overline {x_ {m}}} \}}

.

A partir de F com cláusulas n, construímos um grafo G e então mostramos: F é satisfazível se e somente se G tiver um n-clique.

Construção de G

Sejam nós de G todas as ocorrências literais na fórmula F, mais precisamente todos os pares . ${\ displaystyle (y_ {i, j}, i)}$
As bordas de G são todas as conexões entre ocorrências literais, exceto sozinhas
1. entre duas ocorrências literais em uma e a mesma cláusula - portanto, não conecte e use uma borda ${\ displaystyle (y_ {i, j_ {1}}, i)}$ ${\ displaystyle (y_ {i, j_ {2}}, i)}$
2. entre duas ocorrências literais em que o mesmo literal ocorre uma vez positivo e uma vez negado - ou seja, não e se combinam para um k. ${\ displaystyle (y_ {i_ {1}, j_ {1}}, i_ {1})}$ ${\ displaystyle (y_ {i_ {2}, j_ {2}}, i_ {2})}$ ${\ displaystyle \ {y_ {i_ {1}, j_ {1}}, y_ {i_ {2}, j_ {2}} \} = \ {x_ {k}, {\ overline {x_ {k}}} \}}$

prova

G tem um n-clique ⇒ F é satisfazível: Suponha que G tenha um n-clique. Damos o valor de verdade aos literais de ocorrências literais neste clique . Isso é possível sem contradição por causa da 2ª condição de borda. Como, de acordo com a 1ª condição de borda, não há duas ocorrências literais da mesma cláusula conectadas por uma borda, todas as n de n cláusulas de F tornam-se verdadeiras sob esta atribuição e, portanto, também F. ${\ displaystyle y_ {i, j}}$ ${\ displaystyle (y_ {i, j}, i)}$
F é satisfazível ⇒ G tem um n-clique: Suponha que F seja satisfazível. Então, há uma atribuição de valor de verdade de seus literais, de modo que pelo menos um literal se torne verdadeiro em cada uma das cláusulas . Selecionamos arbitrariamente exatamente uma ocorrência literal com true em cada cláusula . Todos estes aparentemente formam um n-clique em G. ${\ displaystyle (y_ {i, j}, i)}$ ${\ displaystyle y_ {i, j}}$