The Clique Problem
You'll learn what the clique problem is and why it's a fundamental NP-complete problem in graph theory.
What is a Clique?
A clique in an undirected graph is a subset of vertices where every pair of vertices is connected by an edge. Think of it as a group of people at a party where everyone knows everyone else — no strangers within the group.
For example, in a social network graph, a 4-clique means four people who are all mutual friends with each other.
The Decision Problem
The Clique Problem asks: Given a graph G and a number k, does G contain a clique of size at least k?
- Input: A graph G = (V, E) and an integer k
- Question: Is there a complete subgraph with k vertices?
Why It's in NP
This problem clearly belongs to NP because:
- Certificate: A list of k vertices
- Verification: Check every pair among those k vertices has an edge — this takes polynomial time O(k²)
NP-Completeness
The Clique Problem is NP-complete, which means:
- It's in NP (easy to verify solutions)
- Every other NP problem can be reduced to it
This was proven by reducing 3-SAT to Clique. Given a 3-SAT formula, you can construct a graph where a k-clique exists if and only if the formula is satisfiable. This reduction shows that if you could solve Clique efficiently, you could solve all NP problems efficiently.
Practical Implications
No known polynomial-time algorithm exists for finding cliques of arbitrary size. Real-world applications in social networks, bioinformatics, and network security must use approximation algorithms or heuristics.
Key Takeaway: The Clique Problem asks whether a graph contains k mutually connected vertices, and it's NP-complete — proving it requires showing both membership in NP (easy verification) and a reduction from another NP-complete problem like 3-SAT.