dirigido G = (V, E) é um subconjunto V’ contido propriamente em V de vértices, no qual cada par está ligado por uma aresta em E. Em outras palavras, o Clique é um subgrafo completo de G.
o número de vértices que contém. O problema do Clique é o problema de otimização de encontrar um clique de tamanho máximo em um grafo. Por ser um problema de decisão, simplesmente perguntamos se um clique de um dado tamanho k existe no grafo.
dado grafo G=(V, E), usamos o conjunto V’ contido propriamente em V de vértices no clique como um certificado para G. Podemos verificar se V’ é um clique em tempo polinomial verificando se, para cada par u,v pertence a V’, a aresta (u, v) pertence a E.
mostra que o problema do Clique é NP-difícil. O algoritmo de redução começa com uma instância de 3-CNF-SAT. Seja ϕ = C1 ^ C2 ^ … ^ Ck uma fórmula booleana em 3-CNF-SAT com k cláusulas. Para r = 1, 2, …, k, cada cláusula Cr tem exatamente 3 literais distintos l1r, l2r e l3r. Construiremos um grafo G tal que ϕ seja satisfazível se e somente se G tem um clique de tamanho k.
cláusula Cr = l1r, l2r e l3r em ϕ, inserimos uma tripla de vértices v1r, v2r e v3r em V. Inserimos uma aresta entre dois vértices vir e vjs se ambas as afirmativas seguintes valem: • vir e vjs estão em triplas diferentes, isto é, r é diferente de s e • seus literais correspondentes são coerentes, isto é, lir não é a negação de ljs.
cada cláusula Cr contém no mínimo um literal lir ao qual é atribuido 1, e tal literal corresponde a um vértice vir. Escolher um desses literais “verdadeiros” de cada cláusula produz um conjunto de V’ de k vértices. Afirmamos que V’ é um clique. Para quaisquer dois vértices vir, vjs pertencente a V’, onde r é diferente de s, ambos os literais correspondentes, lir e ljs mapeiam para 1 pela atribuição dada e, portanto, os literais não podem ser complementos. Assim, pela construção de G, a aresta (vir, vjs) pertence a E.
tamanho k. Nenhuma aresta em G liga vértices na mesma tripla e, portanto, V’ contém exatamente um vértice por tripla. Podemos atribuir 1 a cada literal lir tal que vir pertença a V’, sem receio de atribuir 1 a um literal e a seu complemento, já que G não contém arestas entre literais incoerentes. Cada cláusula é satisfeita, e portanto, ϕ é satisfeita.
que satisfaz de ϕ tem x2 = 0 e x3 = 1. Um clique correspondente de tamanho k = 3 consiste nos vértices que correspondem a ~x2 da primeira cláusula, x3 da segunda cláusula e x3 da terceira cláusula. Como o clique não contém nenhum vértice correspondente a x1 nem a ~x1, podemos definir x1 como 0 ou 1 nessa atribuição satisfatória.
3-CNF-SAT a uma instância de CLIQUE com uma estrutura específica. Mostramos que CLIQUE é NP-difícil em grafos nos quais os vértices estão restritos a ocorrer em triplas e nos quais não há arestas entre vértices na mesma tripla. Mas essa prova basta?
com uma estrutura especial a instâncias gerais de CLIQUE talvez as instâncias de 3-CNF-SAT que escolhêssemos para iniciar a redução fossem “fáceis”, e portanto não teríamos reduzido um problema NP-difícil a CLIQUE.
e não a solução. Teríamos errado se a redução de tempo polinomial tivesse sido baseada em saber se a fórmula ϕ é o satisfazível, já que não sabemos como decidir se ϕ é satisfazível em tempo polinomial.