Reductions: Solving One Problem by Turning It into Another
A reduction converts inputs of one problem into inputs of another while preserving their answers. Polynomial-time reductions support algorithm reuse and conditional hardness arguments. The conversion, target solver and any solution recovery all contribute to the total cost.
What a learner can do afterwards
- Reduce bipartite matching to maximum flow and state what the conversion costs
- Explain why a polynomial-time conversion is needed to transfer a polynomial-time solving guarantee
- Use the reduction direction to justify algorithm reuse or a conditional hardness argument
1 · Read
You have already turned matching into a flow problem. A reduction from decision problem A to decision problem B converts each input while preserving its yes-or-no answer. Solve the converted input to answer A. For a problem asking for an actual solution, you also need a way to recover that solution from B's output.
For bipartite matching with V vertices and E edges, add a source and sink. Use capacity 1 on source-to-worker, worker-to-job and job-to-sink edges. The network has V + 2 vertices and E + V edges. Building adjacency lists takes O(V + E) time. Use an integral maximum flow: conservation and unit capacities allow at most one selected edge per worker or job. Scan the E middle edges to recover the matching in O(E) time.
Polynomial time means a bound by a fixed power of input length. Count conversion, solving and recovery. A polynomial conversion writes at most polynomially many symbols. If conversion takes n^3 steps, writes at most n^2 symbols, and the target solver takes at most m^2 steps on length m, their combined cost is at most n^3 + n^4. An exponential conversion gives no polynomial guarantee. A tightest bound is the smallest growth order justified by the stated algorithm.
Suppose A reduces to B in polynomial time. A polynomial-time solver for B gives one for A. Conversely, if A has no polynomial-time algorithm, B cannot have one: such a B solver would produce an A solver. This is a conditional argument. The reduction alone does not establish that a particular source lacks a polynomial algorithm.
Check which problem becomes the solver's input. An easy source reducing to a target does not prove the target easy. A source reducing to a target with no polynomial algorithm does not prove the source lacks one. To transfer that lower-bound claim to a new target, the source must already have the lower bound and reduce to the target in polynomial time.
A polynomial reduction from A to B lets B's polynomial solver solve A. If A has no polynomial solver, neither does B. Count construction and recovery costs.
Original lesson, questions and flashcards written for this learning dataset.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.