Clique problem
The clique problem ( with CLIQUE listed ) is a decision problem in graph theory. The clique problem is one of 21 classic NP -complete problems which belong to this class, Richard M. Karp showed in 1972.
Problem
It is asked whether there is a simple graph G and a number n is a clique of minimum size n in G; That is, if G has at least n nodes, all of which are interconnected in pairs.
Set
CLIQUE is NP -complete.
Idea of proof
Polynomialzeitreduktion of 3KNF - SAT to CLIQUE:
Since 3KNF - SAT is NP-complete, then this also applies to CLIQUE.
Sketch of proof
Let F be a formula with n clauses in 3KNF, so 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 n- clique.
Construction of G
- Nodes of G are all Literalvorkommen in the formula F, more precisely all pairs.
- Edges of G are all connections between Literalvorkommen, with the sole exception So not and connect via edge - between two Literalvorkommen in the same clause
- Between two Literalvorkommen, in which the same literal once positively and once negated occurs - ie not connect and if k for a
Evidence
- G has an n- clique F is satisfiable ⇒: Suppose that G has an n- clique. The literals of lying in this clique Literalvorkommen we give the truth value true. This is possible without contradiction because of the second edge condition. Because after the first edge condition no two Literalvorkommen are connected from the same clause by edge, are among this assignment, all true n of n clauses of F and hence also F.
- F is satisfiable ⇒ G has an n- clique: Suppose that F is satisfiable. Then there is a truth assignment to its literals, so that in each of the clauses a literal is at least true. We choose in each clause exactly one arbitrary Literalvorkommen with true from. All these seem to form an n- clique in G.