Clique problem
The clique problem ( notated with CLIQUE ) is a decision problem in graph theory . The clique problem is one of the 21 classical NPcomplete problems , which Richard M. Karp proved in 1972 to belong to this class .
Problem
The question is whether there is a clique of minimum size n in G for a simple graph G and a number n ; that is, whether G has at least n nodes that are all connected in pairs.
sentence
CLIQUE is NPcomplete .
Proof idea
Polynomial time reduction from 3KNFSAT to CLIQUE:
Since 3KNFSAT is NPdifficult , this also applies to CLIQUE. In addition, it can easily be shown that CLIQUE itself lies in NP, so overall it is NPcomplete.
Evidence sketch
Let F be a formula with n clauses in 3KNF, i.e. in conjunctive normal form with at most three literals per clause:
 .
From F with n clauses we construct a graph G and then show: F is satisfiable if and only if G has an nclique.
Construction of G
 Let nodes of G be all literal occurrences in the formula F, more precisely all pairs .
 Edges of G are all connections between literal occurrences, except alone
 between two literal occurrences in one and the same clause  so do not connect and use an edge
 between two literal occurrences in which the same literal occurs once positive and once negated  i.e. not and combine if for a k.
proof
 G has an nclique ⇒ F is satisfiable: Assume that G has an nclique. We give the truth value to the literals of literal occurrences in this clique . This is possible without contradiction because of the 2nd edge condition. Because, according to the 1st edge condition, no two literal occurrences from the same clause are connected by an edge, all n of n clauses of F become true under this assignment and thus also F.
 F is satisfiable ⇒ G has an nclique: Assume that F is satisfiable. Then there is a truth value assignment of its literals so that in each of the clauses at least one literal becomes true . We arbitrarily select exactly one literal occurrence with true in each clause . All of these apparently form an nclique in G.
Examples
Example of an occupancy that can be fulfilled:

Example of an occupancy that cannot be fulfilled:


See also
literature
 Schöning, Uwe: Theoretical Computer Science  in short.  4th edition, corr. Nachdr.  Heidelberg: Spectrum, Akad. Verl., 2003, ISBN 3827410991 .