xxi. Problem Reduction and Modeling

Most hard problems are a known problem in disguise. Modeling is the skill of stripping the story and seeing the structure: what are the objects, what are the choices, what is being optimized, and which known problem has exactly that shape.

The questions that reveal the model

Ask	If yes, think of
Are there objects and pairwise relations?	a graph: vertices = objects, edges = relations
Is each choice “pick one of two” with pairwise constraints?	2-SAT
Are we pairing items from two sides?	bipartite matching / assignment
Are we choosing a subset with “if A then B” and profits/costs?	project selection = minimum cut
Is something “sent” from sources to sinks with capacities?	max flow, min-cost flow
Is it a sequence of decisions with a small state?	DP; or shortest path on the state graph
Is the answer monotone in a parameter?	binary search on the answer
Do we need a longest chain under a partial order?	LIS / Dilworth
Is the cost convex in a count?	Aliens trick, slope trick, min-cost flow
Are the operations reversible and composable?	group / permutation cycles, matrix power

Reduction catalog

Looks like	Is actually	Note
assign workers to jobs, one each, minimum cost	assignment problem (Hungarian / min-cost flow)	Assignment
place non-attacking rooks / cover rows and columns	bipartite matching, König	Bipartite Matching
choose a subset with dependencies to maximize profit	maximum closure = min cut	Flow Modeling
separate two groups with minimum cost of cut pairs	minimum $s$-$t$ cut	Min Cut
minimum number of chains to cover a poset	$n-$ maximum matching (Dilworth)	Bipartite Matching
longest chain of nested envelopes / boxes	LIS after sorting	Sequence DP
minimum moves in a puzzle / grid with keys / states	BFS on the implicit state graph	BFS and DFS
cheapest way with “free” or 0-cost moves	0-1 BFS / Dijkstra on states	Shortest Paths
system of $x_j-x_i\le c$	shortest paths (difference constraints)	Shortest Path Techniques
each variable true/false, clauses of two literals	2-SAT via SCC	2-SAT
connect everything at minimum cost	MST	MST
traverse every edge once	Euler path / circuit	Euler Tours
schedule tasks with prerequisites	topological sort, DAG DP	DAGs
count ways with a sum of sizes	polynomial multiplication / generating functions	Generating Functions
sum over pairs of $f(a_i+b_j)$ or $f(i-j)$	convolution (FFT)	FFT
xor of a subset equal to / maximal	linear algebra over GF(2)	XOR Basis
two players, last move wins, sum of independent games	Sprague–Grundy	Sprague–Grundy
intervals: max non-overlapping, min points to stab	greedy by right end	Interval Problems
repeated function application $f^k(x)$	functional graph, binary lifting	Functional Graphs

Transforming the input

Transformation	Effect
sort the items	order-independent problems become prefix / two-pointer problems
reverse time	deletions become insertions (DSU), “last” becomes “first”
complement	count the bad objects instead of the good ones
prefix sums / differences	range conditions become point conditions
rotate coordinates $(x+y,x-y)$	Manhattan becomes Chebyshev
contract equivalent states	SCC condensation, DSU merging, canonical forms
binary search on the answer	optimization becomes a yes/no feasibility check
process offline in a clever order	sort queries, divide and conquer on time, Mo’s order

Proof: why the two classic reductions are exact

Dilworth via matching. Split each element $v$ into $v^{out}$ and $v^{in}$ and add an edge $u^{out}\to v^{in}$ when $u<v$. A matching is a set of “successor” choices in which each element has at most one successor and one predecessor, so it decomposes the poset into chains; each matched edge reduces the number of chains by one, so the minimum chain cover is $n-$ the maximum matching. (For a minimum cover by chains in the transitive closure, which Dilworth’s theorem counts, the edges must be all comparable pairs, as above.) Project selection. Connect $s\to i$ with capacity $p_i$ for profitable items, $i\to t$ with capacity $c_i$ for costly items, and $i\to j$ with capacity $\infty$ when choosing $i$ requires $j$. A finite cut $(S,T)$ corresponds exactly to a closed set $S\setminus \{s\}$ (no infinite edge leaves it), and its capacity is (profit of unchosen items) + (cost of chosen items) $=$ total profit $-$ (net value of the chosen set). Minimizing the cut maximizes the net value.

Related: Attacking a Problem, 🐬 Before Contest.