Source: Discussion Worksheet 09, EECS 376, University of Michigan
Difficulty: Intermediate to Advanced | Prerequisites: P, NP, NP-Completeness, polynomial-time reductions, and the basics of approximation ratios (covered in the companion study notes on NP-Completeness and Complexity Classes).
This material covers two of the most important techniques in computational complexity: turning a decision oracle into a full search algorithm, and designing (or proving limits on) approximation algorithms for hard problems. Search-to-decision reductions show that if you can answer yes/no efficiently, you can often recover the actual solution efficiently too. Approximation algorithms give you a way to get provably good (though not optimal) answers to NP-Hard problems in polynomial time. Together, these techniques form the practical toolkit for dealing with problems that are believed to have no exact efficient solution.
A decision oracle (yes/no black box) for an NP-Complete problem can be leveraged to find actual solutions by systematically removing parts of the input and asking whether a solution still exists. For optimisation variants like Knapsack, binary search on the answer value turns the decision oracle into an optimiser. On the approximation side, a simple greedy algorithm gives a 1/(Δ+1) approximation for Maximum Independent Set, while general TSP provably cannot be approximated at all (unless P = NP).
Search-to-decision reduction
A technique that converts a decision algorithm (one that answers yes/no) into a search algorithm (one that finds an actual solution). The idea is to iteratively constrain the input, using the decision oracle at each step to check whether a solution still exists.
Think of it as asking a series of yes/no questions that gradually narrow down the answer, like a game of twenty questions.
Decision oracle (black box)
An algorithm D that, given an instance of a decision problem, returns yes or no in polynomial time. In a search-to-decision reduction, you treat D as a subroutine you can call as many times as needed.
Binary search on the answer
A technique for optimisation problems: when the decision oracle answers "is the optimal value at least K?", you can find the exact optimal value by binary-searching over possible values of K, making O(log(max value)) calls to the oracle.
Independent set
A subset S of vertices in a graph such that no two vertices in S are connected by an edge. The Maximum Independent Set (MIS) problem asks for the largest such set.
In simple terms, pick as many vertices as you can without picking any two that are neighbours.
Travelling Salesman Problem (TSP)
Given a set of cities with pairwise distances, find the shortest tour that visits every city exactly once and returns to the start. The Euclidean (metric) version satisfies the triangle inequality; the general version does not.
Triangle inequality
The property that for any three points a, b, c, the direct distance from a to c is at most the distance from a to b plus b to c: d(a,c) ≤ d(a,b) + d(b,c). When this holds, TSP admits constant-factor approximations. When it does not, all bets are off.
Inapproximability
A proof that no polynomial-time algorithm can achieve a certain approximation ratio for a problem, unless P = NP. For general TSP, no finite approximation ratio is achievable.
You are given a black-box decision algorithm D that answers: "Does graph G have a Hamiltonian cycle?" Your task is to find the actual cycle.
The algorithm:
Run D(G). If D says no, output "No Hamiltonian cycle exists" and stop.
For each edge e in G:
Let G' = G with edge e removed.
Run D(G'). If D says yes (a Hamiltonian cycle still exists without e), set G = G'. If D says no (removing e breaks all Hamiltonian cycles), keep e.
After processing all edges, the remaining edges form the Hamiltonian cycle.
Why it works:
At each step, you remove an edge only if the graph still has a Hamiltonian cycle without it. So you never destroy all Hamiltonian cycles. At the end, the edges you kept are exactly those that belong to at least one Hamiltonian cycle, and since you removed every non-essential edge, what remains is a single cycle through all vertices.
Why it is efficient:
The graph has at most O(n²) edges. Each edge requires one call to D, which runs in polynomial time. So the total running time is O(n²) times the running time of D, which is polynomial.
The Knapsack decision problem asks: given items with weights W[i] and values V[i], a capacity C, and a target K, does there exist a subset of items with total weight ≤ C and total value ≥ K? Assume an efficient algorithm D decides this.
Part (a): Finding the optimal value K*
Use binary search on K. The maximum possible value is the sum of all item values, call it V_total.
Set lo = 0, hi = V_total.
While lo < hi:
Set mid = ⌈(lo + hi) / 2⌉.
Run D(W, V, C, mid). If D accepts, set lo = mid. Otherwise set hi = mid - 1.
Output lo as K*.
This makes O(log V_total) calls to D. Since V_total is at most n × (max value) and values are represented in binary, log V_total is polynomial in the input size.
Part (b): Finding the actual subset
Once you know K*, iterate through items one by one:
Start with the full item set and target K*.
For each item i from 1 to n:
Try excluding item i: run D on the remaining items with capacity C and target K*.
If D accepts, exclude item i (it is not needed).
If D rejects, include item i (it is essential). Subtract W[i] from C and V[i] from K*.
Output the included items.
This is the same edge-removal pattern as the HamCycle reduction: tentatively remove a piece, ask the oracle if a solution still exists, and keep the piece only if removing it breaks things. The total number of oracle calls is n, so the algorithm is efficient.
The greedy algorithm for MIS is straightforward:
Start with S = ∅ and G' = G.
While G' has vertices:
Pick an arbitrary vertex v.
Add v to S.
Remove v and all its neighbours (and their edges) from G'.
Output S.
S is always a valid independent set because whenever you add v, you remove all its neighbours, so no two vertices in S are adjacent.
Part (a): Bounding |U| ≤ |S| · Δ
Let U = V \ S be the vertices removed in step 2 that were not selected for S (the neighbours). Each vertex added to S causes at most Δ neighbours to be removed, where Δ is the maximum degree in G. Since |S| vertices are selected, at most |S| · Δ vertices are removed as neighbours. Therefore |U| ≤ |S| · Δ.
Part (b): The 1/(Δ+1) approximation
The total number of vertices is |V| = |S| + |U|. From part (a): |V| ≤ |S| + |S| · Δ = |S| · (Δ + 1).
So |S| ≥ |V| / (Δ + 1).
The optimal independent set OPT has |OPT| ≤ |V| (trivially). Therefore:
|S| ≥ |V| / (Δ + 1) ≥ |OPT| / (Δ + 1)
This means the greedy algorithm returns an independent set of size at least 1/(Δ+1) times the optimum. For a maximisation problem, that is a 1/(Δ+1)-approximation.
Real-world note: This is a weak guarantee when Δ is large (in a dense graph, 1/(Δ+1) is tiny). Better approximation algorithms exist for special graph classes, but MIS on general graphs is notoriously hard to approximate.
For TSP in Euclidean space (where the triangle inequality holds), a 2-approximation exists. The question asks you to prove that no α-approximation exists for general TSP (for any α > 1), unless P = NP.
The reduction:
Given an instance G = (V, E) of HamCycle:
Construct a complete weighted graph f(G) on the same vertex set V.
For edges in E (the original graph), assign weight 1.
For edges not in E, assign weight K (a large number to be chosen).
The argument:
If G has a Hamiltonian cycle, then f(G) has a TSP tour of cost exactly |V| (using only weight-1 edges).
If G does not have a Hamiltonian cycle, then any TSP tour in f(G) must use at least one edge of weight K, so the tour cost is at least |V| - 1 + K.
Now set K large enough that an α-approximation algorithm A would distinguish these two cases. Specifically, choose K such that:
α · |V| < |V| - 1 + K
This holds for K > (α - 1) · |V| + 1, which is polynomial in the input size.
With this choice:
If G has a Hamiltonian cycle: OPT = |V|, so A returns a tour of cost ≤ α · |V| < |V| - 1 + K.
If G has no Hamiltonian cycle: OPT ≥ |V| - 1 + K, so A returns a tour of cost ≥ |V| - 1 + K.
By checking whether A's output cost is below or above the threshold, you decide HamCycle in polynomial time. Since HamCycle is NP-Complete, this would imply P = NP.
The takeaway: The triangle inequality is not just a technical convenience for TSP approximation. Without it, the problem becomes so hard that no polynomial-time algorithm can guarantee any finite approximation ratio (unless the entire NP-Complete landscape collapses).
Students think search-to-decision reductions require a clever algorithm. The pattern is almost always the same: try removing one element, ask the oracle if a solution still exists, keep it only if removing it breaks things. The cleverness is in proving correctness, not inventing the method.
Students forget that binary search on the Knapsack value works because the values are integers. If values were continuous, you could not binary search in polynomial time. The binary representation of the integers bounds the number of search steps.
In the MIS approximation proof, students try to compare |S| directly to |OPT| without going through |V|. The correct route is |V| = |S| + |U| ≤ |S|(Δ+1), then |OPT| ≤ |V| ≤ |S|(Δ+1).
In the TSP inapproximability proof, students sometimes set K = α or K = 2. K must be chosen to create a gap large enough that the α-approximation cannot bridge it. The correct choice depends on α and |V|.
⚠️ Search-to-decision reductions are a staple exam topic. Be ready to apply the "remove and re-query" pattern to a new NP-Complete problem you have not seen before.
⚠️ The Knapsack binary-search technique is a standard building block. It appears any time you need to find the optimal value of a problem that has a decision version.
⚠️ Approximation ratio proofs require you to bound the algorithm's output relative to OPT. For maximisation problems, you show |A(x)| ≥ (1/α) · |OPT|. Make sure you know which direction the inequality goes.
⚠️ The TSP inapproximability argument is a template for proving that approximation implies P = NP. The technique (constructing a gap instance where the approximation algorithm would distinguish YES from NO) applies to other problems too.
True or False: In the HamCycle search-to-decision reduction, you remove vertices one at a time. _____
Fill in the blank: To find the optimal Knapsack value K* using a decision oracle, you use _____ on the value parameter.
True or False: The greedy MIS algorithm always finds the maximum independent set. _____
Fill in the blank: The greedy MIS algorithm achieves a _____-approximation, where Δ is the maximum degree.
True or False: General TSP (without the triangle inequality) can be approximated within a factor of 1000 in polynomial time, assuming P ≠ NP. _____
Answers: 1. False (you remove edges, not vertices). 2. binary search. 3. False (it is an approximation, not exact). 4. 1/(Δ+1). 5. False (no finite factor is achievable unless P = NP).
Q: In the HamCycle search-to-decision reduction, why do you remove edges rather than vertices?
A: Removing a vertex would also remove its incident edges and could destroy multiple potential cycle edges at once, making it impossible to isolate which edges belong to the Hamiltonian cycle. Removing one edge at a time lets you test each edge individually.
Q: Why does binary search on Knapsack values take polynomial time, even though the maximum value can be exponentially large?
A: The values are represented in binary. Binary search takes O(log V_total) steps. Since V_total ≤ n × 2^b where b is the number of bits per value, log V_total is O(n·b), which is polynomial in the input size.
Q: Why is the MIS approximation ratio 1/(Δ+1) rather than 1/Δ?
A: The +1 accounts for the selected vertex itself. When you pick a vertex v and remove it along with its neighbours, you remove at most Δ neighbours (the degree bound) plus v itself. So each selection accounts for at most Δ+1 vertices total.
Q: In the TSP inapproximability proof, what goes wrong if you set K = 2 instead of a value depending on α and |V|?
A: With K = 2, the gap between the YES case (cost = |V|) and the NO case (cost ≥ |V| - 1 + 2 = |V| + 1) is too small. An α-approximation with α > 1 could return a tour of cost up to α · |V| in the YES case, which might exceed |V| + 1 for large |V|, making the two cases indistinguishable.
Q: Describe the general pattern for a search-to-decision reduction.
A: Start with the full input. Iteratively try removing one component (an edge, an item, a variable assignment). After each removal, query the decision oracle. If the oracle says yes, the component is dispensable, so keep it removed. If the oracle says no, the component is essential, so restore it. After processing all components, the essential ones form the solution.
The search-to-decision technique here builds on the NP-Completeness foundations from the first half of the worksheet (and the companion study notes). Understanding that verification is easy while search is hard is the motivation for the entire reduction approach.
The TSP inapproximability argument connects to reduction theory more broadly: you are reducing HamCycle to TSP-approximation, showing that if one is easy, the other is too. This is the same reduction framework used throughout EECS 376.
The MIS approximation connects to graph theory and vertex cover (the complement of an independent set is a vertex cover), which appears in other EECS 376 worksheets.
search-to-decision reduction, decision oracle, black box algorithm, Hamiltonian cycle, HamCycle, Knapsack problem, binary search on answer, optimisation from decision, independent set, maximum independent set, MIS, greedy algorithm, vertex cover, TSP, travelling salesman problem, general TSP, Euclidean TSP, metric TSP, triangle inequality, inapproximability, gap reduction, approximation ratio, NP-Hard, P = NP, EECS 376, foundations of computer science, University of Michigan