Reductions: Solving One Problem by Turning It into Another
A reduction converts every instance of one problem into an instance of another, so a solver for the second answers the first. Read forwards it reuses an algorithm, and read backwards it transfers hardness from a problem nobody can solve quickly.
What a learner can do afterwards
- Reduce bipartite matching to maximum flow and state what the conversion costs
- Explain why a reduction has to run quickly for the argument to mean anything
- Say which direction of a reduction proves easiness and which proves hardness
1 · Read
You already know flow finds a maximum through a network. A reduction converts every instance of one problem into an instance of another. Then a solver for the second problem answers the first one for free.
To match workers to jobs, build a flow network with a source, a sink, and unit capacities, then run max flow. The conversion costs almost nothing beside building the small network, and the matching reads straight off the used edges.
Read forwards, a reduction reuses an algorithm: if the target is easy, your problem is easy too. Read backwards, it transfers hardness: if your problem is hard, the target must be hard as well. Easiness flows one way, hardness the other.
Two checks before you claim anything. The conversion itself must run quickly, or the argument means nothing. And the direction must match the claim: the wrong way round proves nothing about the problem you care about.
Convert cheaply to a solved problem, reuse its solver forwards, and transfer hardness only backwards.
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.