Difficulty: Intermediate | Prerequisites: NP and polynomial-time verifiers, graph theory basics (vertices, edges, subgraphs), understanding of polynomial-time reductions (≤p).
This material sits at the heart of computational complexity theory. You are learning how to prove that problems are NP-Complete, which means showing they are among the hardest problems in NP. The technique here is polynomial-time reduction: you take a problem already known to be NP-Complete and transform its instances into instances of your target problem. If you can do that in polynomial time, your target is at least as hard. This is also where the "search from decision" paradigm appears, showing that a black-box yes/no solver can be leveraged to actually find solutions.
CLIQUE is NP-Complete because INDEPENDENT-SET (a known NP-Hard problem) reduces to it by taking the complement graph. A black-box CLIQUE decider can be used to find the actual maximum clique by first binary-searching for the clique size, then iteratively removing non-essential vertices.
Clique
A subset of vertices in an undirected graph where every pair of vertices is connected by an edge. A k-clique is a clique of size k. In simple terms, a clique is a group of nodes that are all friends with each other.
Independent set
A subset I ⊆ V of vertices in a graph G such that no two vertices in I share an edge. Think of it as the opposite of a clique: a group of nodes where nobody is connected to anybody else in the group.
Complement graph (G̅ or G')
Given a graph G = (V, E), the complement graph G' = (V, E') has the same vertices but E' contains an edge between u and v if and only if (u, v) ∉ E. Every edge is flipped: present becomes absent, absent becomes present. In simple terms, you take the original graph and swap all the connections: connected pairs become disconnected, and disconnected pairs become connected.
NP-Complete
A problem that is both in NP (verifiable in polynomial time) and NP-Hard (every problem in NP can be reduced to it in polynomial time). Proving NP-Completeness requires showing both membership in NP and hardness via reduction.
Polynomial-time mapping reduction (≤p)
A function f computable in polynomial time such that x ∈ A if and only if f(x) ∈ B. Written A ≤p B, meaning "A is no harder than B." If A is NP-Hard and A ≤p B, then B is also NP-Hard.
Search from decision
The technique of using a decision oracle (yes/no black box) to solve the corresponding search problem (finding the actual solution). You use the oracle repeatedly, each time narrowing down the answer.
This was proved in discussion (taken as given here). The certificate is the set of k vertices; the verifier checks that every pair shares an edge. Runs in O(k²) time.
The key insight is that an independent set in G corresponds exactly to a clique in the complement graph G'.
The reduction function f:
On input ⟨G = (V, E), k⟩:
Define V' = V (keep the same vertices)
Define E' = {(u, v) : u, v ∈ V, u ≠ v, (u, v) ∉ E} (flip every edge)
Return ⟨(G' = (V', E'), k)⟩
Why f is a valid polynomial-time reduction:
Polynomial-time computable:
Step 1 takes O(|V|) time
Step 2 loops over all vertex pairs and checks edge membership: O(|V|²|E|) time
Step 3 takes O(1) time
Forward direction: ⟨G, k⟩ ∈ INDEPENDENT-SET implies G has an independent set S of size at least k. For all distinct u, v ∈ S, there is no edge between them in G, meaning (u, v) ∉ E. By construction of E', all such pairs have (u, v) ∈ E'. So the same vertices form a clique of size at least k in G'. Therefore ⟨G', k⟩ ∈ CLIQUE.
Backward direction: ⟨G', k⟩ ∈ CLIQUE implies G' has a clique C of size at least k. Every pair of vertices in C is connected in G'. By construction of E', that means no pair of vertices in C was connected in the original graph G. So C forms an independent set of size at least k in G. Therefore ⟨G, k⟩ ∈ INDEPENDENT-SET.
Since INDEPENDENT-SET is NP-Hard and INDEPENDENT-SET ≤p CLIQUE, CLIQUE is NP-Hard. Combined with CLIQUE ∈ NP, CLIQUE is NP-Complete.
Given a black-box decider D that efficiently decides CLIQUE (i.e., D answers "does G have a clique of size at least k?"), you can find the actual maximum clique.
Algorithm:
On input ⟨G = (V, E)⟩:
Initialise k* = 0
For k going from |V| down to 1: run D on ⟨G, k⟩. If D accepts, set k* = k and stop the loop.
If k* = 0, return an empty graph.
For each vertex v ∈ V: remove v and its adjacent edges from G, then run D on ⟨G, k*⟩. If D rejects, add v back along with its edges.
Return G (the remaining graph is the maximum clique).
Why this works:
Steps 1-2 find the size k* of the maximum clique by trying each possible size from largest to smallest. The first value D accepts is the maximum.
Step 4 strips away every vertex that is not needed for a clique of size k*. If removing a vertex still lets a k*-clique exist, that vertex was not part of the clique, so it stays removed. If removing it destroys the k*-clique, D rejects and the vertex is added back.
After processing every vertex, only the clique vertices remain.
Efficiency:
Step 2 calls D at most |V| times. Step 4 calls D at most |V| times. Each call to D is efficient by assumption. Total: O(|V|) calls to an efficient decider, so the whole algorithm runs in polynomial time.
Complement graph edge set:
E' = {(u, v) : u, v ∈ V, u ≠ v, (u, v) ∉ E}
CLIQUE language:
CLIQUE = {⟨G, k⟩ : G is an undirected graph that has a k-clique subgraph}
INDEPENDENT-SET language:
INDEPENDENT-SET = {⟨G, k⟩ | G has an independent set of size k}
Reduction function:
f(⟨G = (V, E), k⟩) = ⟨(G' = (V, E'), k)⟩ where E' is the complement edge set. Note that k does not change.
Clique-finding appears in social network analysis (finding tightly connected communities), bioinformatics (identifying protein interaction clusters), and telecommunications (frequency assignment). The complement-graph relationship between cliques and independent sets is used in scheduling problems, where finding an independent set in a conflict graph identifies a set of tasks that can run simultaneously without conflicts.
Students often think that showing a problem is in NP is enough to prove NP-Completeness. It is not. You must also show NP-Hardness via a reduction from a known NP-Hard problem.
Students sometimes get the reduction direction backwards. To show CLIQUE is NP-Hard, you reduce FROM a known hard problem (INDEPENDENT-SET) TO CLIQUE, not the other way around. The reduction direction matters: A ≤p B means "if I can solve B, I can solve A," so B is at least as hard as A.
When constructing the complement graph, students sometimes forget that the vertex set stays the same. Only the edges change.
In the search-from-decision algorithm, students sometimes confuse which direction to iterate k. You go from |V| downward so the first acceptance gives you the maximum clique size, not just any clique size.
⚠️ Being able to prove NP-Completeness through reduction is a core exam skill. Expect to be given a new problem and asked to reduce a known NP-Complete problem to it.
⚠️ The complement graph construction (INDEPENDENT-SET ≤p CLIQUE) is one of the cleanest reductions in the course. Know it cold.
⚠️ "Search from decision" is a recurring pattern. The CLIQUE version here is a template: find the optimal parameter value, then iteratively remove unnecessary components. The same pattern appears for PARTITION and other problems.
⚠️ When writing a reduction proof, you must show three things: (1) the reduction function runs in polynomial time, (2) yes-instances map to yes-instances (forward direction), and (3) yes-instances in the target map back to yes-instances in the source (backward direction).
True or False: To prove CLIQUE is NP-Complete, it suffices to show CLIQUE ≤p INDEPENDENT-SET. Answer: False. You need to reduce FROM a known NP-Hard problem TO CLIQUE, not the other direction.
Fill in the blank: In the complement graph G', an edge exists between u and v if and only if ______ in the original graph G. Answer: there is no edge between u and v.
True or False: The search-from-decision algorithm for CLIQUE makes O(|V|²) calls to the decider. Answer: False. It makes O(|V|) calls: at most |V| to find k* and at most |V| to prune vertices.
True or False: A clique of size k in G corresponds to an independent set of size k in the complement graph G'. Answer: True.
Fill in the blank: In the vertex-removal step of the search-from-decision algorithm, if D accepts after removing vertex v, this means v is ______ for the maximum clique. Answer: not required (not part of the clique).
Q: Describe the reduction function that proves INDEPENDENT-SET ≤p CLIQUE, and explain why the forward direction works.
A: The reduction takes ⟨G = (V, E), k⟩ and returns ⟨G' = (V, E'), k⟩ where E' is the complement of E. The forward direction works because if G has an independent set S of size k, then no two vertices in S share an edge in G. By construction of E', every pair in S does share an edge in G'. So S is a clique of size k in G'.
Q: Suppose you have a black-box decider D for CLIQUE. You run D on ⟨G, 5⟩ and it accepts, and on ⟨G, 6⟩ it rejects. What can you conclude?
A: The maximum clique in G has size exactly 5. D accepting ⟨G, 5⟩ means G has a clique of at least 5. D rejecting ⟨G, 6⟩ means G has no clique of size 6 or larger.
Q: In the search-from-decision algorithm, why is it important to iterate through vertices one at a time rather than removing multiple vertices at once?
A: Removing multiple vertices simultaneously could remove vertices from different maximum cliques. A vertex might be unnecessary for one maximum clique but essential for another. By testing one at a time and keeping those that are essential, you ensure you preserve at least one complete maximum clique.
Q: What is the time complexity of the entire search-from-decision algorithm for finding a maximum clique, expressed in terms of |V| and the running time T(D) of the decider?
A: O(|V| × T(D)). The algorithm makes at most 2|V| calls to D (at most |V| to find k* and at most |V| to prune vertices), each costing T(D).
This connects to VERTEX-COVER because the VERTEX-COVER to INDEPENDENT-SET reduction (from Section Notes 7) uses a similar complement relationship: a vertex cover of size k corresponds to an independent set of size |V| - k. The chain of reductions runs VERTEX-COVER ≤p INDEPENDENT-SET ≤p CLIQUE.
The search-from-decision technique reappears in the PARTITION problem (HW 8 Q2) and is a general paradigm in complexity theory: any NP-Complete decision problem has a corresponding search problem solvable with polynomially many oracle calls.
The idea of graph complements also appears in graph colouring, where the chromatic number of a graph relates to the clique number of its complement.
Related Terms / Search Tags
clique problem, independent set problem, complement graph, graph complement, NP-Complete, NP-Hard, polynomial-time reduction, Karp reduction, many-one reduction, search from decision, decision to search, maximum clique, EECS 376, foundations of computer science, computational complexity, graph theory, NP-Completeness proof, reduction direction