Clique problem

The clique problem ( notated with CLIQUE ) is a decision problem in graph theory . The clique problem is one of the 21 classical NP-complete 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 NP-complete .

Proof idea

Polynomial time reduction from 3KNF-SAT to CLIQUE:

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

Since 3KNF-SAT is NP-difficult , this also applies to CLIQUE. In addition, it can easily be shown that CLIQUE itself lies in NP, so overall it is NP-complete.

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:

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

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

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

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

• Let nodes of G be all literal occurrences in the formula F, more precisely all pairs . ${\displaystyle (y_{i,j},i)}$
• Edges of G are all connections between literal occurrences, except alone
  1. between two literal occurrences in one and the same clause - so do not connect and use an edge ${\displaystyle (y_{i,j_{1}},i)}$ ${\displaystyle (y_{i,j_{2}},i)}$
  2. between two literal occurrences in which the same literal occurs once positive and once negated - i.e. not and combine if for a 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}}}\}}$

proof

• G has an n-clique ⇒ F is satisfiable: Assume that G has an n-clique. 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. ${\displaystyle y_{i,j}}$ ${\displaystyle (y_{i,j},i)}$
• F is satisfiable ⇒ G has an n-clique: 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 n-clique in G. ${\displaystyle (y_{i,j},i)}$ ${\displaystyle y_{i,j}}$

Examples

Example of an occupancy that can be fulfilled: ${\displaystyle ({\overline {x_{1}}}\lor x_{1}\lor {\overline {x_{2}}})\land (x_{2}\lor x_{1}\lor {\overline {x_{2}}})}$ The constructed graph.	Example of an occupancy that cannot be fulfilled: ${\displaystyle ({\overline {x_{1}}}\lor {\overline {x_{1}}}\lor x_{2})\land (x_{2}\lor x_{2}\lor x_{1})\land ({\overline {x_{2}}}\lor {\overline {x_{2}}}\lor {\overline {x_{2}}})}$ The constructed graph.
There are seven different 2-cliques in the graph.	There is not a single 3-clique in the graph.

See also

• Complexity class
• NP (complexity class)
• Satisfiability problem of propositional logic (SAT)

literature

• Schöning, Uwe: Theoretical Computer Science - in short. - 4th edition, corr. Nachdr. - Heidelberg: Spectrum, Akad. Verl., 2003, ISBN 3-8274-1099-1 .