Composition of Gap Reductions

Definition

Composition of Gap Reductions

Suppose $f$ is a gap-introducing reduction from SAT to a minimisation problem ${\Pi }_1$ with threshold $g_1$ and factor $\alpha$. Suppose $h$ is a gap-preserving reduction from ${\Pi }_1$ to a maximisation problem ${\Pi }_2$, with the same source threshold $g_1$ and factor $\alpha$, and target threshold $g_2$ and factor $\beta$.

Then $h\circ f$ is a gap-introducing reduction from SAT to ${\Pi }_2$:

$$\begin{array}{rl}F\text{ satisfiable}& ⟹{\mathrm{OPT}}_{{\Pi }_2}(h(f(F)))\ge g_2(h(f(F))),\\ F\text{ unsatisfiable}& ⟹{\mathrm{OPT}}_{{\Pi }_2}(h(f(F)))<\beta (|h(f(F))|)g_2(h(f(F))).\end{array}$$

Consequently ${\Pi }_2$ has no polynomial-time $\beta (|I_2|)$-approximation unless $P=NP$. Analogous compositions apply to the other objective directions.

Follow Each Case Through Both Maps

Write $I_1=f(F)$, $I_2=h(I_1)$, and $O_i={\mathrm{OPT}}_{{\Pi }_i}(I_i)$. The important feature is not merely that the arrows connect: the middle inequalities must be exactly the premises needed by $h$.

Proof

Satisfiable source formula

Because $f$ introduces the source gap, satisfiable $F$ gives $O_1\le g_1(I_1)$. This is the yes-premise of $h$, so $O_2\ge g_2(I_2)$.

Unsatisfiable source formula

Because $f$ introduces the source gap, unsatisfiable $F$ gives $O_1>\alpha (|I_1|)g_1(I_1)$. This is the no-premise of $h$, so $O_2<\beta (|I_2|)g_2(I_2)$.

Polynomial time and hardness

A polynomial-time computation of $f$ has polynomial output length. Running polynomial-time $h$ on that output still takes polynomial time in $|F|$.

A hypothetical $\beta$-approximation on $I_2$ returns a value $v_2\ge \beta g_2(I_2)$ in the yes-case. In the no-case, feasibility forces $v_2\le O_2<\beta g_2(I_2)$. Comparing $v_2$ with $\beta g_2(I_2)$ would decide SAT in polynomial time.

Why Matching Thresholds Matters

Suppose $f$ promises no-instances with $O_1>120$, but $h$ preserves only no-instances with $O_1>150$. A possible output with $O_1=130$ satisfies the first promise but not the second. We cannot apply the no-case implication of $h$.

Exact equality of the middle parameters is sufficient. More generally, it is enough that each output range of $f$ is contained in the corresponding promised input range of $h$.