Cairn
guides · cross-cutting lens, not tied to one category

↩ back to Guides

Reductions in Disguise

The pattern: the same computation under a different name

Four pairs of entries on this site look, read cold, like they have nothing to do with each other — a matching problem and a flow network, a boolean-satisfiability question and a graph-reachability one, a range query and a tree-ancestor query, two string-search algorithms with different names. In every pair, one page turns out to already be the other — not an approximation, not a loose analogy, but the literal same computation reached by a construction that's provable or a collapse that's measured. Three distinct shapes recur below: build a bridge, then hand off to an algorithm this site already built and verified; reduce to an easier instance of the same problem, not a different problem entirely; and collapse, where the general algorithm degenerates into the specific one at some boundary with nothing hand-built at all. Every claim in the three sections below is a quote or a measured number from the two source pages involved — this page only lines them up side by side for the first time.

Build a bridge, then hand off

Bipartite Matching reduces to Max Flow. There's no capacity, no source, no sink anywhere in the original problem statement — just two sides of a graph and the question of the largest one-to-one pairing between them. The bridge: add a source with a capacity-1 edge to every left node, a sink with a capacity-1 edge from every right node, keep every original edge at capacity 1. Bipartite Matching's own Why section proves the connection both directions — any matching gives a flow of the same size, and any integer flow in this specific network decomposes cleanly into a matching of the same size — then runs Edmonds-Karp's own augmenting-path loop unmodified to find the answer. Its own closing line: "the two are the same algorithm wearing different vocabulary, not two different algorithms that happen to agree."

2-SAT reduces to Strongly Connected Components. A 2-SAT clause (a ∨ b) is two implications, ¬a → b and ¬b → a, already contrapositives of each other; translating every clause this way builds an implication graph over one node per literal. 2-SAT's own Why it works section: "the whole satisfiability question collapses to: run SCC on the implication graph, and check whether any variable's two literals landed in the same component." The page runs Tarjan's algorithm — "the same Tarjan's-algorithm SCC routine from this site's own Strongly Connected Components page" — not a reimplementation, and even reads the satisfying assignment straight off the SCC computation's own closing order. The result is O(V + E) because the real work is a subroutine this site already built and verified, not a new traversal of its own.

Reduce to an easier instance of the same problem

Not every reduction lands on an unrelated algorithm. General Range-Minimum Query reduces to a more restricted instance of range-minimum query, via two intermediate stops. First: build a Cartesian Tree from the array in O(n) (a monotonic-stack pass, heap-ordered by value) — and the lowest common ancestor of any two array positions in that tree lands exactly on the range-minimum between them. Cartesian Tree's own page is explicit about what that buys and what it doesn't: "that full O(1) picture chains three separate pieces together: this page's O(n) tree construction, an Euler tour of the finished tree reduced to a restricted array where consecutive values only ever differ by exactly ±1, and an O(1)-query scheme built specifically for that restricted shape — a much easier problem than general range-minimum." ±1 RMQ is that second and third piece: block decomposition gets the restricted array's own build down to O(n), and one precomputed lookup table per block shape gets its query down to true O(1). The interesting twist, compared to the two reductions above: the destination isn't a different problem with a different name — it's the same range-minimum question, just asked of an array shape so constrained (every step ±1) that the general algorithm's own hard part dissolves.

Collapse: the general algorithm becomes the special one

The first three reductions above are all deliberate constructions — someone has to notice the connection and build the bridge. Aho-Corasick, given exactly one pattern, needs no bridge at all: it degenerates into KMP automatically. Aho-Corasick's own measured break-even section: "with k=1 the trie is a single chain and its failure links are exactly KMP's own LPS table, so the two scan passes are byte-for-byte identical" — confirmed by running both pages' own shipped reference implementations against an 8-character pattern over random text from 50 to 5,000 characters, with the scan cost matching at every length tested, not just on average. Nobody constructed this correspondence by hand; it falls out the moment the general multi-pattern machinery is handed the narrowest input it can take. The same section measures what happens the instant that stops being true: at k=2 patterns the two algorithms' outputs and costs diverge, and the automaton's extra build cost is paid back within a fraction of the very first text scanned (0.16 texts at k=2, n=100) rather than needing many texts to amortize.

Try it: match the disguise

Eight cards, four hidden pairs — the four reductions above, split into their two names. Click two cards you think are secretly the same computation; a correct pair locks in and reveals the one-line argument plus both source pages. Cards are reshuffled with this site's own Fisher–Yates Shuffle on load and on "Shuffle again."

pairs found: 0 / 4
Click two cards you think are secretly the same computation.

Pitfalls

A reduction proven in only one direction doesn't prove equivalence. Showing "every matching gives a flow of the same size" only proves the max flow is at least the max matching — an upper bound masquerading as an answer. Bipartite Matching's own Why section doesn't stop there: it also proves the reverse, that every integer flow in that specific network decomposes into a matching of the same size, before calling the two equal. A reduction that only ever argues one direction has proven a bound, not an identity — worth checking which one any new "X reduces to Y" claim actually established before trusting it.

Correct — even asymptotically optimal — isn't the same as simplest. Routing Bipartite Matching through the flow-network reduction above and running Dinic's algorithm on it reaches exactly O(E√V), the same bound Hopcroft-Karp reaches directly, without ever building a flow network, "discovered independently... Hopcroft and Karp published this bipartite-only, flow-network-free version in 1973, two years before Dinic's more general algorithm." The reduction loses nothing asymptotically here — but it still drags in machinery (source, sink, capacities, a general max-flow loop) that buys nothing once the problem is already known to be bipartite matching specifically. A correct reduction is a proof of equivalence, not a recommendation about which side to actually implement.

A collapse holds exactly at its boundary, not past it. Aho-Corasick at k=1 is byte-identical KMP, measured. At k=2 it is already a genuinely different, more capable structure — a branching trie with failure links that can jump between different patterns, not "KMP with an extra pattern bolted on" — and the site's own break-even measurement shows the crossover from "never pays off" to "pays off within a fraction of one text" happens at that exact single step from k=1 to k=2. The collapse is a coincidence at one specific point in the parameter space, not a smooth family that degrades gracefully on either side of it.

Where this shows up on this site