Difficulty: Intermediate-Advanced | Prerequisites: NP and NP-hard definitions, graph theory basics (cliques, colourings), modular arithmetic
Polynomial-time mapping reductions are the standard tool for proving a new problem is NP-hard. The logic: if you can transform any instance of a known NP-hard problem into an instance of your new problem (in polynomial time, preserving yes/no answers), then your new problem is at least as hard as the known one. This review covers two such reductions from the EECS 376 final review session: COLORING to CLIQUE-COVER, and 3-COLORING to MOD-3SAT. You should already be comfortable with the definitions of NP and NP-hard, basic graph colouring, complement graphs, and arithmetic modulo 3. If any of those are fuzzy, revisit them before working through these reductions.
To show CLIQUE-COVER is NP-hard, take the complement of the input graph so that colour classes (independent sets in the original) become cliques. To show MOD-3SAT is NP-hard, encode each edge as a modular subtraction equation that is satisfied exactly when the two endpoints receive different colours. Both reductions are polynomial-time and preserve the yes/no answer.
Polynomial-time mapping reduction (Karp reduction)
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 simple terms, this means you can convert any instance of problem A into an instance of problem B quickly, and the answer is preserved.
Clique
A subset of vertices in an undirected graph where every pair of vertices is connected by an edge. Think of it as a group of nodes that are all mutual 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 number of vertices. Think of it as partitioning (or covering) the graph into fully connected groups.
CLIQUE-COVER
The decision problem: given (G, k), does G have a clique cover of size at most k?
k-colourable (graph colouring)
A graph is k-colourable if you can assign one of k colours to each vertex so that no two adjacent vertices share the same colour. Think of it as colouring a map so no two neighbouring countries have the same colour.
COLORING
The decision problem: given (G, k), is G k-colourable?
3-COLORING
The decision problem: given G, is G 3-colourable? Known to be NP-hard.
Complement graph
Given G = (V, E), its complement G' = (V, E') has an edge between u and v exactly when G does not. In simple terms, you flip every edge: connected pairs become disconnected, and vice versa.
MOD-3SAT
The decision problem: given a system S of mod-3 equations (each of the form xᵢ ± xⱼ ≡ c mod 3) and an integer k, is there an assignment of values from {0, 1, 2} to the variables that satisfies exactly k equations?
Z₃
The integers modulo 3, i.e. {0, 1, 2}, with addition and subtraction wrapping around. For example, 2 + 2 ≡ 1 (mod 3).
Given an instance (G, k) of COLORING, construct f(G, k) = (G', k) where G' is the complement of G.
Build G' = (V, E') where (u, v) is in E' if and only if (u, v) is not in E.
Pass k through unchanged.
Constructing the complement graph takes O(|V|²) time: iterate over every pair of vertices and include the edge exactly when the original graph does not have it. This is polynomial in the size of the input.
Forward direction: (G, k) in COLORING implies (G', k) in CLIQUE-COVER.
Suppose G is k-colourable. Consider the k colour classes, where each class is the set of all vertices assigned the same colour. In G, vertices of the same colour are never adjacent (by the colouring rule), so each colour class is an independent set in G. In the complement G', an independent set in G becomes a clique (all those non-edges become edges). Therefore the k colour classes form k cliques that together cover every vertex.
Backward direction: (G', k) in CLIQUE-COVER implies (G, k) in COLORING.
Suppose G' has a clique cover of size at most k, say {C₁, ..., Cₖ}. Each Cᵢ is a clique in G', which means within Cᵢ every pair of vertices is adjacent in G'. That means within Cᵢ no pair of vertices is adjacent in G, so Cᵢ is an independent set in G. Assign all vertices in Cᵢ colour i. Since each Cᵢ is an independent set in G, no two same-coloured vertices are adjacent, giving a valid k-colouring of G.
Independent sets and cliques are complementary notions with respect to complement graphs. Colour classes in a proper colouring are independent sets, and independent sets in G are cliques in G'. This duality is the engine of the entire reduction.
Given a graph G = (V, E):
Create one variable xᵢ in Z₃ for each vertex vᵢ. Each variable takes values in {0, 1, 2}, representing the three colours.
For each edge (vᵢ, vⱼ) in E, create the equation: xᵢ - xⱼ ≢ 0 (mod 3). Equivalently, since a single mod-3 equation of the form a ⊕ b = c can only express one congruence, encode this as: xᵢ - xⱼ ≡ c (mod 3) for some constant, but we need to be careful. The key is that xᵢ - xⱼ ≢ 0 mod 3 exactly when the endpoints have different colours.
More precisely: for each edge (u, v), create the equation xᵤ - xᵥ ≡ c (mod 3). Since the equation format requires a specific constant c, and we want the equation to be satisfied when the two colours differ, we use the subtraction operation. The equation xᵤ - xᵥ ≡ 0 (mod 3) is satisfied only when xᵤ = xᵥ, so it is not satisfied when they differ. We can exploit this: for each edge, write the equation xᵤ - xᵥ ≡ 0 (mod 3). This equation is satisfied when the endpoints have the same colour.
Set k = 0, meaning we want zero of these equations satisfied. Then (S, 0) is in MOD-3SAT if and only if there exists an assignment where none of the equations xᵤ - xᵥ ≡ 0 is satisfied, i.e. every pair of adjacent vertices has different colours, which is exactly a valid 3-colouring.
Alternatively (and more elegantly): for each edge (u, v), create the equation xᵤ - xᵥ ≡ 0 (mod 3), and set k = 0. The system S has m = |E| equations. An assignment satisfies exactly 0 equations precisely when every adjacent pair has distinct colours.
The reduction creates n variables (one per vertex) and m equations (one per edge). Writing the system takes O(n + m) time, which is polynomial.
Forward: G is 3-colourable implies (S, 0) is in MOD-3SAT.
If G has a valid 3-colouring, assign each xᵢ the colour of vertex vᵢ (mapping colours to 0, 1, 2). For every edge (u, v), the endpoints have different colours, so xᵤ - xᵥ ≢ 0 (mod 3). Every equation is unsatisfied, so exactly 0 equations are satisfied.
Backward: (S, 0) is in MOD-3SAT implies G is 3-colourable.
If there is an assignment with exactly 0 satisfied equations, then for every edge (u, v) we have xᵤ - xᵥ ≢ 0 (mod 3), so xᵤ ≠ xᵥ. Interpreting the variable values as colours gives a valid 3-colouring of G.
The subtraction operation in Z₃ naturally encodes "different colour": a - b ≡ 0 (mod 3) if and only if a = b. By asking for zero satisfied equations of this form, you are asking that no two adjacent vertices share a colour.
Students often confuse the direction of the reduction. To show problem B is NP-hard, you reduce a known NP-hard problem A to B (A ≤_p B), not the other way around. Reducing B to A would show A is at least as hard as B, which is the wrong conclusion.
The size of a clique cover is the number of cliques, not the total number of vertices across all cliques. The problem sheet emphasises this, which means it is a common source of lost marks.
In the CLIQUE-COVER reduction, students sometimes forget to take the complement. Colour classes are independent sets in G, not cliques. You need the complement to turn them into cliques.
For MOD-3SAT, students sometimes set k = |E| (wanting all equations satisfied) instead of k = 0. Whether you use k = 0 or k = |E| depends on what your equations encode. If each equation says "same colour," you want zero satisfied. If each equation says "different colour," you want all satisfied. Be consistent.
⚠️ Reductions are a recurring exam topic in EECS 376. Expect to be given a new language and asked to prove it NP-hard by reducing a known NP-hard problem to it.
⚠️ You must argue both efficiency (the transformation runs in polynomial time) and correctness (the if-and-only-if direction). Missing either direction is an incomplete proof.
⚠️ The complement-graph trick (independent set ↔ clique) appears in many reductions. Recognise it quickly.
⚠️ Modular arithmetic reductions (like MOD-3SAT) test whether you can translate a graph-colouring constraint into an algebraic one. The exam may vary the modulus or the operation.
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: In the complement graph G', an independent set in G becomes a ______. (Clique.)
True or false: The size of a clique cover counts the total number of vertices in all cliques combined. (False, it counts the number of cliques.)
Fill in the blank: xᵤ - xᵥ ≡ 0 (mod 3) holds if and only if xᵤ ______ xᵥ. (Equals.)
True or false: A polynomial-time reduction must preserve yes-instances and no-instances in both directions. (True.)
Q: Define the reduction f for COLORING ≤_p CLIQUE-COVER and state its running time.
A: f(G, k) = (G', k) where G' is the complement of G. The complement can be constructed in O(|V|²) time, which is polynomial.
Q: In the CLIQUE-COVER reduction, why does a colour class in G become a clique in G'?
A: A colour class is an independent set in G (no two vertices share an edge). In the complement G', every non-edge of G becomes an edge, so every pair in the colour class is now adjacent, forming a clique.
Q: For the MOD-3SAT reduction, what equation do you write for an edge (u, v), and what value of k do you use?
A: Write the equation xᵤ - xᵥ ≡ 0 (mod 3) for each edge. Set k = 0. An assignment satisfying zero of these equations means every adjacent pair has different values, which corresponds to a valid 3-colouring.
Q: Suppose the graph G has 5 vertices and 7 edges. How many variables and equations does the MOD-3SAT instance have?
A: 5 variables (one per vertex) and 7 equations (one per edge).
Q: Why is it wrong to reduce CLIQUE-COVER to COLORING when trying to show CLIQUE-COVER is NP-hard?
A: That reduction would show COLORING is at least as hard as CLIQUE-COVER, which is the wrong direction. To show CLIQUE-COVER is NP-hard, you need to reduce a known NP-hard problem (COLORING) to CLIQUE-COVER, proving that CLIQUE-COVER is at least as hard.
This material connects directly to NP-completeness proofs: once you show a problem is both NP-hard (via reduction) and in NP (via a polynomial-time verifier), you have shown it is NP-complete. The complement-graph technique reappears when reducing between INDEPENDENT SET, VERTEX COVER, and CLIQUE. The algebraic flavour of the MOD-3SAT reduction also connects to constraint-satisfaction problems and to the broader study of how Boolean satisfiability generalises to other algebraic domains.
NP-hard, NP-complete, polynomial-time reduction, Karp reduction, mapping reduction, graph colouring, k-colouring, 3-colouring, clique, clique cover, complement graph, independent set, vertex cover, COLORING, CLIQUE-COVER, MOD-3SAT, 3-COLORING, modular arithmetic, Z₃, constraint satisfaction, EECS 376, Foundations of Computer Science, UMich