Introduction

Alright, graph fans, it’s time for the Clique Problem, another rockstar of NP-completeness. The question: given a graph $G$ and an integer $k$, does $G$ contain a clique (a set of mutually adjacent vertices) of size $k$? Spotting a clique feels tough, and indeed, it’s NP-complete.

Problem Statement

Given an undirected graph $G = (V, E)$ and a target $k \in \mathbb{N}$, the Clique decision problem asks:

Is there a subset $C \subseteq V$ with $|C| = k$ such that every pair of vertices in $C$ is connected by an edge?

Formally:

$$ \mathrm{CLIQUE} = {\langle G, k \rangle \mid G \text{ has a clique of size } k}. $$

Example

Consider the graph with vertices $V = {1,2,3,4}$ and edges:

$E = {{1,2}, {1,3}, {2,3}, {2,4}}.$

  • Question: Is there a clique of size 3? Check ${1,2,3}$: all edges ${1,2}, {1,3}, {2,3}$ exist, so yes!

  • Question: Is there a clique of size 4? No, vertex 4 isn’t connected to 1 or 3, so it can’t join the triangle.

NP-Completeness Proof Sketch

  1. Clique is in NP: Given a candidate set $C$, we can verify in $O(k^2)$ time that all pairs are edges.

  2. Hardness (Reduction from 3-SAT): Given a 3-CNF formula $f = C_1 \land C_2 \land \cdots \land C_m$ with each clause $C_j = (ℓ_{j1} \lor ℓ_{j2} \lor ℓ_{j3})$, build a graph:

    1. Vertices: For each literal a copy $v_{j,i}$ representing the $i$-th literal of clause $C_j$.
    2. Edges: Connect $v_{j,i}$ to $v_{j’,i’}$ (where $j \neq j’$) if and only if those literals are not contradictory (i.e., not one $x$ and the other $\lnot x$).
    3. Set $k = m$: We want one vertex per clause.

    A clique of size $m$ picks one literal from each clause such that no two picked literals clash, which exactly corresponds to a satisfying assignment for $f$.

Therefore, since 3-SAT is NP-hard, Clique is NP-hard too. Combine with Clique being in NP, and we get NP-completeness.

Why It Matters

  • Benchmark Problem: Clique is a classic target for testing exact and approximation algorithms in combinatorial optimization.
  • Network Analysis: Finding densely connected subgraphs (cliques) is central in social network analysis, bioinformatics, etc.

Wrap-Up

The Clique Problem nails down that in graphs, just asking “Is there a fully connected subgraph of size $k$?” is as hard as any NP problem. Next in the series: our grand finale, The P vs NP Problem!