Gap-Preserving Reduction

Definition

Gap-Preserving Reduction

A gap-preserving reduction is a polynomial-time instance map $h:I_1\mapsto I_2$ that sends the two promised optimum ranges of a source optimisation problem ${\Pi }_1$ into two separated optimum ranges of a target problem ${\Pi }_2$.

Fix positive threshold functions $g_1(I_1),g_2(I_2)$ and factor functions $\alpha (|I_1|),\beta (|I_2|)$. The thresholds must be computable and comparable in polynomial time. Write $O_i={\mathrm{OPT}}_{{\Pi }_i}(I_i)$.

Minimisation to maximisation

With $\alpha \ge 1$ and $0<\beta \le 1$, require, for every $I_1$,

$$\begin{array}{rl}{O}_1\le g_1(I_1)& ⟹O_2\ge g_2(I_2),\\ O_1>\alpha g_1(I_1)& ⟹O_2<\beta g_2(I_2).\end{array}$$

Factors are evaluated at their respective instance sizes. A nontrivial multiplicative gap has $\alpha >1$ on the minimisation side and $\beta <1$ on the maximisation side.

What Is Preserved?

Think of the source task as distinguishing two kinds of instance: those with a small optimum and those with a much larger optimum. The reduction lets us make this distinction by examining a different optimisation problem instead.

Follow the two cases separately

Use the concrete thresholds $g_1=100$, $\alpha =1.2$, $g_2=50$, and $\beta =0.8$. Thus $\alpha g_1=120$ and $\beta g_2=40$.

The same polynomial-time procedure $h$ transforms every source instance $I_1$ into a target instance $I_2$. It does not first compute $O_1$ or decide which case holds. Instead, we prove that its outputs satisfy these conditional guarantees:

• Whenever $O_1\le 100$, the output has $O_2\ge 50$.
• Whenever $O_1>120$, the output has $O_2<40$.

The reduction preserves which promised case holds, not the numerical value of the optimum or the numerical width of the gap. The source’s low-optimum case becomes the target’s high-optimum case because the objective changes from minimisation to maximisation. “Yes” labels the chosen case; it does not mean the same inequality direction in both problems.

If $g_1(I_1)<O_1\le \alpha g_1(I_1)$, neither premise holds. The definition places no extra optimum requirement on $h(I_1)$ in this intermediate range. The reduction must still run and produce a valid target instance.

Unlike a L-reduction, this definition does not require a backward conversion of arbitrary feasible solutions. To transfer gap hardness, the target algorithm’s returned value can be enough to distinguish the two source cases.

Other Objective Directions

For each source and target, choose the corresponding pair of ranges:

Objective	Yes range	No range
Minimise	$O\le g$	$O>\gamma g$, with $\gamma \ge 1$
Maximise	$O\ge g$	$O<\gamma g$, with $0<\gamma \le 1$

A gap-preserving reduction maps the source yes range into the target yes range and the source no range into the target no range. This specifies minimisation-to-minimisation, maximisation-to-maximisation, and maximisation-to-minimisation without changing the underlying idea.

Transferring the Ability to Distinguish

For the minimisation-to-maximisation case, suppose a target algorithm guarantees a feasible value $v_2\ge \beta O_2$.

Source yes-instance

If $O_1\le g_1$, preservation gives $O_2\ge g_2$. Therefore
$v_2\ge \beta O_2\ge \beta g_2.$

Source no-instance

If $O_1>\alpha g_1$, preservation gives $O_2<\beta g_2$. Feasibility gives
$v_2\le O_2<\beta g_2.$

Thus testing $v_2\ge \beta g_2$ distinguishes the source’s two promised cases. This becomes an NP-hardness result only when distinguishing those source cases is already NP-hard—for example, through a gap-introducing reduction. The existence of $h$ alone does not establish hardness.

The gap keeps approximate answers distinguishable

Continue with $g_2=50$ and $\beta =0.8$. We cannot necessarily compute the target optimum $O_2$, but we can inspect the value $v_2$ of the solution returned by a hypothetical $0.8$-approximation.

In the yes-case, the guarantee gives $v_2\ge 0.8O_2\ge 40$. In the no-case, even an optimal solution has value below $40$, so every feasible output satisfies $v_2<40$.

We only use this test on source instances satisfying one of the two promises. An input in the intermediate source range need not be classified meaningfully. The numerical thresholds illustrate the mechanism, not a construction between particular optimisation problems.

Composition

The composition theorem combines a SAT-to-${\Pi }_1$ gap-introducing reduction with a compatible ${\Pi }_1$-to-${\Pi }_2$ gap-preserving reduction. The source thresholds must match: the first reduction must output instances in the ranges that the second reduction promises to preserve.

Example

Different gaps can encode the same two answers

Suppose the source minimisation promise is $O_1\le 100$ or $O_1>120$. A gap-preserving map could guarantee target maximisation optima $O_2\ge 50$ or $O_2<40$, respectively. Here $\alpha =1.2$ and $\beta =0.8$.

A target $0.8$-approximation returns at least $40$ on source yes-instances; every feasible target value is below $40$ on source no-instances. Comparing the returned value with $40$ distinguishes the source cases.

If $O_1=110$, neither source promise holds. The definition does not say on which side of $40$ the target algorithm’s output must fall. These numerical thresholds illustrate the guarantees; they do not construct a reduction between particular problems.