Problem. CLIQUE [CLIQUE]

Figure 1: Simple Clique

Given G=(V,E)G = \left( {V,E} \right) and kk, does there exist U⊆VU \subseteq V with |U|≥k|U| \geq k such that {u,v}∈E\left\{ {u,v} \right\} \in E for all distinct vertices u,v∈Uu,v \in U?

CLIQUE={⟨G,K⟩:Ghas a clique of sizek}\text{CLIQUE} = \left\{ {\left\langle {G,K} \right\rangle:G\ \text{has a clique of size}\ k} \right\}

  • No specification on size: in our example above, there are cliques of size 0 through 3
Theorem.

CLIQUE is NP-complete: i.e. CLIQUE is NP-hard, and CLIQUE is in NP.

Proof.

CLIQUE is in NP: because there exists a verifier that can check a possible clique in polytime.

CLIQUE is NP-hard: because 3SAT (known NP-hard problem) reduces to CLIQUE. How can we do that?

Proof. 3SAT≤PCLIQUE\text{3SAT}\underset{P}{\leq}\text{CLIQUE} (reduction)

x∈3SATx \in \text{3SAT} maps to f(x)∈CLIQUEf(x) \in \text{CLIQUE}

  • If x=⟨φ⟩x = \left\langle \varphi \right\rangle where φ\varphi is a satisfiable 3CNF formula, then f(x)=⟨G,k⟩f(x) = \left\langle {G,k} \right\rangle where GG has a clique of size kk.

x∉3SATx \notin \text{3SAT} maps to f(x)∉CLIQUEf(x) \notin \text{CLIQUE}

  • If x=⟨φ⟩x = \left\langle \varphi \right\rangle where φ\varphi has no satisfiable assignments, then f(x)=⟨G,k⟩f(x) = \left\langle {G,k} \right\rangle where GG has no clique of size kk.
  • junk can map to junk
Figure 2: Complex Clique

We can show 3SAT can be solved by finding a clique of size kk.

  • Connect every vertex in a block to every other vertex that is not its inverse.
  • Then, every clique of size kk is a possible satisfiable assignment.
  • We can’t have xix_{i} and xi_x_{i}^{\_} both being true: which is represented by no connecting edges.

We still need to “decode” f(x)∈Bf(x) \in B to x∈Ax \in A… i.e. f(x)∈CLIQUE⇒x∈3SATf(x) \in \text{CLIQUE}\Rightarrow x \in \text{3SAT}.

  • Let UU be a clique of size kk. We must divy it up so that there is exactly one vertex in each group.
  • Given a f(x)∈CLIQUEf(x) \in \text{CLIQUE} constructed from a 3SAT\text{3SAT} problem, then we find a satisfying x∈3SATx \in \text{3SAT}.

Aside: suppose we want to ensure there is a clique of at least size k−1k - 1. We can make a separate, disconnected clique of k−1k - 1 vertices. What’s this useful for? Don’t know yet…