1.18 Reductions

A reduction transforms one problem into another problem. It is a way to reuse algorithms and transfer difficulty. If problem A can be converted into problem B, and we already know how to solve B, then we can solve A by translating the input, running the solver for B, and translating the output back.

Reductions are useful in two directions. For algorithm design, they let you solve a new problem with a known algorithm. For lower bounds and hardness, they show that a problem is at least as hard as another problem.

Problem

You have a problem that resembles a known problem, but the connection is not exact. You need to make the connection precise so that an existing algorithm or lower bound applies.

Solution

Use a reduction template:

solve_A(input_A):
  input_B = transform_A_to_B(input_A)
  output_B = solve_B(input_B)
  output_A = transform_B_to_A(output_B)
  return output_A

A valid reduction must preserve correctness:

input_A has answer yes if and only if input_B has answer yes

For optimization problems, it must preserve the objective value or provide a controlled way to recover the objective for the original problem.

Example: Two Sum as Set Lookup

Problem A:

Given an array A and target t, decide whether two distinct elements sum to t.

Known problem B:

Set membership:
Given a set S and value x, decide whether x is in S.

Reduction idea:

While scanning the array, ask whether the complement t - A[i] has already appeared.

two_sum(A, t):
  seen = empty set

  for x in A:
    if t - x in seen:
      return true
    add x to seen

  return false

The original pair-sum problem is reduced to repeated set membership queries.

Correctness depends on the order of operations. We check the complement before inserting x, so the algorithm never uses the same occurrence twice.

Example: Longest Common Subsequence as Dynamic Programming

Problem A:

Given strings X and Y, find the length of their longest common subsequence.

Reduction idea:

Convert the original problem into subproblems over prefixes.

State:

dp[i][j] = LCS length of X[0..i-1] and Y[0..j-1]

The problem is reduced to a table of smaller prefix problems. The final answer is dp[n][m].

This is a reduction within the same problem family. Many dynamic programming algorithms can be understood this way: a large instance is reduced to smaller indexed instances with known dependencies.

Example: Bipartite Matching as Max Flow

Problem A:

Given a bipartite graph with left side L and right side R,
find the maximum number of disjoint matched pairs.

Known problem B:

Maximum flow.

Construct a flow network:

source -> each vertex in L        capacity 1
each edge L -> R                  capacity 1
each vertex in R -> sink          capacity 1

Every unit of flow corresponds to one matched pair. The capacity constraints ensure that each vertex is used at most once. Therefore a maximum flow gives a maximum matching.

This reduction lets us use any correct max-flow algorithm to solve bipartite matching.

Reductions for Lower Bounds

Reductions can also show that a problem is difficult.

Suppose problem A is known to require at least Omega(n log n) time in a model. If we can reduce A to problem B efficiently, then a very fast algorithm for B would imply a very fast algorithm for A. If that contradicts the lower bound for A, then B must also be hard.

The direction matters:

A reduces to B

means:

A can be solved using a solver for B.

So B is at least as hard as A, up to the cost of the transformation.

Reduction Checklist

A reduction should answer these questions:

Complexity Accounting

If the transformation from A to B costs O(f(n)), and the solver for B costs O(g(n)), then the total cost is usually:

O(f(n) + g(n))

When the transformed instance has a different size, state that explicitly.

Example:

The graph construction creates n + 2 vertices and m + 2n edges.

Then the max-flow complexity should be expressed in terms of those new parameters.

Common Pitfalls

Do not reduce in the wrong direction. If you want to solve A using B, you need a transformation from A instances to B instances.

Do not ignore the cost of transformation. A reduction that creates a huge instance may destroy the intended efficiency.

Do not assume similar-looking problems reduce cleanly. The transformation must preserve all constraints.

Do not lose witnesses. If the original problem asks for an actual solution, the reduction must show how to recover it from the target output.

Takeaway

A reduction is a correctness-preserving translation between problems. It lets you reuse known algorithms, organize dynamic programming states, and transfer lower bounds. A good reduction states the source problem, target problem, input transformation, output recovery, correctness argument, and total complexity.