Difficulty: Advanced | Prerequisites: NP, NP-hardness, complement graphs, independent sets, cliques, graph colouring basics
Polynomial-time mapping reductions are the main tool for proving that a new problem is NP-hard. The idea: if you can efficiently transform every instance of a known-hard problem into an instance of your new problem, the new problem is at least as hard. This section of the EECS 376 final review practises two such reductions, COLORING to CLIQUE-COVER and 3-COLORING to MOD-3SAT, both built on the relationship between independent sets and cliques in complement graphs. You should already be comfortable with NP, NP-hardness, complement graphs, and the CLIQUE-to-IS reduction.
To show a problem is NP-hard, reduce a known NP-hard problem to it in polynomial time and prove the reduction is correct (both directions of the if-and-only-if). The two worked examples here both exploit the fact that an independent set in a graph is a clique in its complement, and vice versa. The correctness proofs follow a standard two-direction pattern: show that a yes-instance maps to a yes-instance, and that a yes-instance of the output implies a yes-instance of the input.
Polynomial-time mapping reduction (Karp reduction, ≤p)
A function f computable in polynomial time such that x is in language A if and only if f(x) is in language B. Written A ≤p B. In plain terms, it is a fast translator that turns any instance of one problem into an equivalent instance of another.
NP-hard
A problem H is NP-hard if every problem in NP can be reduced to H in polynomial time. Think of it as: at least as hard as the hardest problems whose solutions can be checked quickly.
Clique
A subset of vertices in an undirected graph where every pair of vertices is connected by an edge. In simple terms, a group of nodes that are all friends with each other.
Independent set
A subset of vertices in an undirected graph where no two vertices share an edge. The opposite of a clique: none of them are directly connected.
Complement graph (G̅)
The graph on the same vertex set where an edge exists between u and v in G̅ exactly when it does not exist in G, and vice versa. Think of it as flipping every connection: friends become strangers and strangers become friends.
Clique cover
A collection of cliques C = {C₁, ..., Cₖ} such that every vertex in the graph belongs to at least one clique in C. The "size" of the cover is the number of cliques, not the total number of vertices.
k-colourable graph
A graph whose vertices can each be assigned one of k colours so that no two adjacent vertices share a colour. Each colour class forms an independent set.
Mod-3 system of equations
A set of equations over ℤ₃ = {0, 1, 2}, each of the form aⱼ ⊕ bⱼ ≡ cⱼ (mod 3), where ⊕ is addition or subtraction. The modular-arithmetic analogue of a Boolean satisfiability instance.
MOD-3SAT
The language {(S, k) : S is a mod-3 system with an assignment that satisfies exactly k equations}. It asks whether you can hit a precise count of satisfied equations, not just "all" or "any."
CLIQUE-COVER = {(G, k) : G is an undirected graph with a clique cover of size ≤ k}.
COLORING = {(G, k) : G is an undirected, k-colourable graph}.
COLORING is known to be NP-hard. The goal is to define a polynomial-time mapping reduction f such that (G, k) ∈ COLORING if and only if f(G, k) ∈ CLIQUE-COVER.
The key observation: if G is k-colourable, its vertices split into k independent sets (one per colour). An independent set in G is a clique in the complement graph G̅. So we define:
f(G, k) = (G̅, k)
where G̅ is the complement graph of G.
Constructing G̅ requires iterating over all pairs of vertices and flipping edges. For a graph on n vertices this takes O(n²) time, which is polynomial.
(⟹) Suppose (G, k) ∈ COLORING.
G is k-colourable, so its vertices partition into k independent sets V₁, ..., Vₖ (one per colour). No two vertices in the same set share an edge in G. By definition of the complement, every pair of vertices within each Vᵢ is connected in G̅, so each Vᵢ is a clique in G̅. The collection {V₁, ..., Vₖ} covers all vertices, so (G̅, k) ∈ CLIQUE-COVER.
(⟸) Suppose f(G, k) = (G̅, k) ∈ CLIQUE-COVER.
G̅ has a clique cover {C₁, ..., Cₖ} in which every vertex appears in at least one Cᵢ. Each Cᵢ is a clique in G̅, which means the same set is an independent set in G. Assigning a unique colour to each Cᵢ gives a valid k-colouring of G, so (G, k) ∈ COLORING.
3-COLORING = {G : G is a graph that is 3-colourable}.
MOD-3SAT = {(S, k) : S is a mod-3 system with an assignment satisfying exactly k equations}.
3-COLORING is NP-hard. Each vertex maps to a variable, each colour maps to an element of ℤ₃.
For each vertex v, create a variable xᵥ in ℤ₃. For each edge e = (u, v), add two equations to the system S:
xᵤ − xᵥ ≡ 1 (mod 3)
xᵤ − xᵥ ≡ 2 (mod 3)
Set the budget k = |E| (the number of edges).
The intuition: when two vertices have different colours, their difference mod 3 is either 1 or 2, never 0. So exactly one of the two equations per edge is satisfied, giving exactly |E| satisfied equations in total.
The reduction creates one variable per vertex and two equations per edge. Both counts are linear in the size of the input graph, so the construction runs in polynomial time.
xᵤ | xᵥ | xᵤ − xᵥ (mod 3) |
|---|---|---|
0 | 0 | 0 |
0 | 1 | 2 |
0 | 2 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
1 | 2 | 2 |
2 | 0 | 2 |
2 | 1 | 1 |
2 | 2 | 0 |
Notice: the difference is 0 exactly when the two values match. When they differ, the difference is 1 or 2 (never both).
(⟹) Suppose G ∈ 3-COLORING.
Assign each xᵥ the ℤ₃ value corresponding to v's colour. Adjacent vertices have different colours, so xᵤ ≠ xᵥ, which means xᵤ − xᵥ ≡ 1 or ≡ 2 (mod 3), but not both. Exactly one of the two equations per edge is satisfied, so the total number of satisfied equations is |E|. Therefore (S, |E|) ∈ MOD-3SAT.
(⟸) Suppose f(G) = (S, k) ∈ MOD-3SAT.
An assignment satisfies exactly |E| equations. Since xᵤ − xᵥ can equal either 1 or 2 but not both, exactly one equation per edge must be satisfied. That means xᵤ ≠ xᵥ for every edge, so translating the assignment back to colours yields a valid 3-colouring. Hence G ∈ 3-COLORING.
Instead of two equations per edge, create one equation per edge: xᵤ − xᵥ ≡ 0 (mod 3), and set k = 0. A valid 3-colouring makes every such equation unsatisfied (different colours means the difference is never 0), so exactly 0 equations are satisfied. Conversely, 0 satisfied equations forces all adjacent pairs to differ, which is a valid colouring.
Students often confuse the size of a clique cover (the number of cliques) with the total number of vertices in those cliques. Size counts cliques, not vertices.
When reducing A to B, students sometimes build the reduction in the wrong direction. You are transforming instances of A into instances of B, not the other way around. If you want to show B is NP-hard, reduce a known-hard A to B.
Forgetting to prove both directions of correctness. A valid reduction proof requires (⟹) and (⟸). Showing only one direction does not establish equivalence.
In the MOD-3SAT reduction, students sometimes assume xᵤ − xᵥ can equal both 1 and 2 simultaneously for the same pair. It cannot: the difference is a single value in ℤ₃.
⚠️ Reductions are the bread and butter of NP-hardness proofs on exams. Expect to be given a new language and asked to reduce a known NP-hard problem to it.
⚠️ The complement-graph trick (independent set ↔ clique) appears repeatedly. Know it cold.
⚠️ Efficiency arguments are often worth easy marks. State the time complexity of constructing the reduction output and note that it is polynomial.
⚠️ Correctness proofs must be bidirectional. Label your directions clearly ((⟹) and (⟸)) and state what you are assuming and what you are concluding in each.
⚠️ MOD-3SAT-style reductions test whether you can encode a graph constraint as an algebraic one. Practise translating "adjacent vertices must differ" into equations.
True or False: To show problem B is NP-hard, you reduce B to a known NP-hard problem A. (False, you reduce A to B.)
Fill in the blank: An independent set in G corresponds to a ______ in the complement graph G̅. (clique)
True or False: The size of a clique cover counts the total number of vertices across all cliques. (False, it counts the number of cliques.)
Fill in the blank: In ℤ₃, if xᵤ = 1 and xᵥ = 2, then xᵤ − xᵥ ≡ ______ (mod 3). (2)
True or False: A correct reduction proof only needs to show the forward direction (⟹). (False, both directions are required.)
Q: Define the reduction from COLORING to CLIQUE-COVER and explain why it runs in polynomial time.
A: f(G, k) = (G̅, k), where G̅ is the complement of G. Constructing G̅ requires checking all O(n²) vertex pairs and flipping edges, which is polynomial.
Q: In the COLORING-to-CLIQUE-COVER reduction, why does a valid k-colouring of G imply a clique cover of size k in G̅?
A: Each colour class is an independent set in G. In the complement graph, the same set of vertices forms a clique (every non-edge in G becomes an edge in G̅). The k colour classes therefore give k cliques that cover all vertices.
Q: For the MOD-3SAT reduction from 3-COLORING, how many equations are created per edge, and what budget k is used?
A: Two equations per edge (xᵤ − xᵥ ≡ 1 and xᵤ − xᵥ ≡ 2, both mod 3). The budget is k = |E|. Exactly one of the two is satisfied when the endpoints have different colours.
Q: In the alternative MOD-3SAT reduction, the budget is k = 0. Explain why 0 satisfied equations corresponds to a valid 3-colouring.
A: Each equation is xᵤ − xᵥ ≡ 0 (mod 3), which is satisfied when the two endpoints have the same colour. If 0 equations are satisfied, no adjacent pair shares a colour, which is exactly the definition of a valid colouring.
Q: Why is it not enough to prove only the forward direction of a reduction's correctness?
A: The reduction must be an if-and-only-if: yes-instances map to yes-instances, and non-yes-instances map to non-yes-instances. Proving only one direction leaves open the possibility that the reduction is not faithful in the other direction, so the NP-hardness conclusion does not follow.
This material builds directly on the CLIQUE ≤p INDEPENDENT-SET reduction covered earlier in EECS 376. The complement-graph duality between cliques and independent sets is the same idea reused here for CLIQUE-COVER.
Graph colouring reappears in the randomised algorithms unit (the COLORFUL-TRIANGLE problem), where random colour assignments are analysed via linearity of expectation rather than worst-case reductions.
The structure of reduction correctness proofs (both directions, explicit if-and-only-if) is the same pattern used in undecidability proofs for Turing machines, so practising it here pays off in that section too.
polynomial-time reduction, Karp reduction, mapping reduction, ≤p, NP-hard, NP-complete, clique cover, graph colouring, k-colourable, chromatic number, complement graph, independent set, clique, COLORING, CLIQUE-COVER, MOD-3SAT, 3-COLORING, modular arithmetic, ℤ₃, mod-3 equations, EECS 376, foundations of computer science, University of Michigan, final review