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.
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.
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.
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.
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."
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.