Linear Reduction

Definition

Linear Reduction

Let ${\Pi }_1$ and ${\Pi }_2$ be two optimisation problems. A linear reduction from ${\Pi }_1$ to ${\Pi }_2$ consists of polynomial-time computable functions $f$ and $g$ and constants $\alpha ,\beta >0$. The same functions and constants must satisfy the following conditions for every instance $I_1$ of ${\Pi }_1$.

Here $f_{{\Pi }_i}(I_i,x_i)$ denotes the objective value of solution $x_i$ for instance $I_i$ of ${\Pi }_i$, and ${\mathrm{OPT}}_{{\Pi }_i}(I_i)$ denotes the optimal objective value of $I_i$.

Instance conversion: bound the optimum

The function $f$ maps $I_1$ to an instance $f(I_1)$ of ${\Pi }_2$ such that

$${\mathrm{OPT}}_{{\Pi }_2}\left(\underset{\text{instance of }{\Pi }_2}{\underbrace{f(I_1)}}\right)\le \alpha {\mathrm{OPT}}_{{\Pi }_1}(I_1).$$

Thus the optimum for $f(I_1)$ in ${\Pi }_2$ is at most $\alpha$ times the optimum for $I_1$ in ${\Pi }_1$.

Schematic lengths for non-negative objective values; equality is allowed.

Solution conversion: bound the error

For every feasible solution $x_2$ of $f(I_1)$, the function $g$ produces a feasible solution $g(I_1,x_2)$ of $I_1$ such that

$$\begin{array}{rl}& |{\mathrm{OPT}}_{{\Pi }_1}(I_1)-f_{{\Pi }_1}(I_1,\underset{\text{solution of }{I}_1\text{ in }{\Pi }_1}{\underbrace{g(I_1,x_2)}}\left)\right|\\ & \le \beta |{\mathrm{OPT}}_{{\Pi }_2}(f(I_1))-f_{{\Pi }_2}(\underset{\text{instance of }{\Pi }_2}{\underbrace{f(I_1)}},x_2\left)\right|.\end{array}$$

The absolute error of $g(I_1,x_2)$ in ${\Pi }_1$ is at most $\beta$ times the absolute error of $x_2$ in ${\Pi }_2$.

Schematic error lengths; if $x_2$ has zero error, then $g(I_1,x_2)$ must also have zero error.

Both conversions run in polynomial time; finding $x_2$ is not part of the reduction.

Why a Karp Reduction Is Not Enough

A Karp reduction preserves the yes/no answer of a decision problem. For approximation, we need more: if a target solution is close to optimal, its converted source solution must also be close to optimal. Preserving only exact answers does not give that guarantee.

An L-reduction therefore has two directions of computation:

1. Send the source instance $I_1$ to the target instance $I_2=f(I_1)$.
2. Given any feasible target solution $x_2$, convert it back to a source solution $x_1=g(I_1,x_2)$.

The target algorithm supplies $x_2$; the reduction does not find it. This separation lets us ask: what would a good algorithm for the target problem give us for the source problem?

“Linear” refers to the two multiplicative bounds on optima and errors. It does not require linear running time or a linear map on the input. The constants $\alpha$ and $\beta$ are fixed for the reduction, not chosen separately for each instance.

What the Two Constants Control

Assume non-negative objective values. For one fixed instance and one fixed pair of solutions, abbreviate

$$O_1={\mathrm{OPT}}_{{\Pi }_1}(I_1),O_2={\mathrm{OPT}}_{{\Pi }_2}(I_2),v_1=f_{{\Pi }_1}(I_1,x_1),v_2=f_{{\Pi }_2}(I_2,x_2).$$

The definition now reads

$$\underset{\text{control the objective scale}}{\underbrace{O_2\le \alpha O_1}},\underset{\text{control the absolute error}}{\underbrace{|O_1-v_1|\le \beta |O_2-v_2|}}.$$

• $\beta$ bounds how many units of error the conversion can introduce per unit of target error. In particular, a target optimum has error zero and must convert to a source optimum.
• $\alpha$ prevents the target optimum $O_2$ from being arbitrarily large compared with $O_1$. A small percentage of a huge $O_2$ could otherwise allow a large error compared with $O_1$.

For example, suppose $O_1=100$, $O_2=200$, $\alpha =2$, and $\beta =1$. A target solution of value $v_2=190$ has error $10$. For maximisation, its converted solution must have $v_1\ge 90$. A $95\%$ target guarantee has become a $90\%$ source guarantee: the absolute error is unchanged, but the source optimum is smaller.

Transferring an Approximation Guarantee

The dedicated inapproximability-transfer theorem derives the forbidden target ratio and distinguishes strict hardness thresholds from boundary guarantees. The calculation below states its algorithmic direction.

Maximisation to maximisation

Suppose an L-reduction from ${\Pi }_1$ to ${\Pi }_2$ has constants $\alpha ,\beta >0$, and both problems maximise non-negative objective values. If a polynomial-time target algorithm guarantees $v_2\ge \rho O_2$, where $0\le \rho \le 1$, then the composed source algorithm guarantees

$$v_1\ge (1-\alpha \beta (1-\rho ))O_1.$$

The bound is informative when its coefficient is positive.

Proof

The target guarantee first bounds the target’s missing value:

$$O_2-v_2\le (1-\rho )O_2.$$

Convert the target solution using $g$. Feasible maximisation values never exceed the optimum, so the absolute errors in the definition become ordinary differences:

$$\begin{array}{rlrl}{O}_1-v_1& \le \beta (O_2-v_2)& & \text{solution conversion}\\ & \le \beta (1-\rho )O_2& & \text{target guarantee}\\ & \le \alpha \beta (1-\rho )O_1& & \text{optimum bound}.\end{array}$$

Subtracting this upper bound on the missing value from $O_1$ gives the claim. Computing $f$, running the target algorithm, and computing $g$ are all polynomial-time operations.

The quantity $1-\rho$ is the target’s allowed relative error. The product $\alpha \beta$ bounds how much that relative error can grow when we return to the source problem. The displayed ratio formula is for maximisation to maximisation; the definition also applies to minimisation, but the ratio calculation must then be adjusted.

Showing Inapproximability

Approximation algorithms transfer from target to source. By contradiction, hardness transfers from source to target.

Suppose it is known that no polynomial-time source algorithm achieves a ratio strictly greater than $r$, unless $P=NP$. A target algorithm with ratio

$$\rho >1-\frac{1-r}{\alpha \beta }$$

would give

$$1-\alpha \beta (1-\rho )>r$$

for the source, contradicting that hardness theorem. Therefore no such target algorithm exists unless $P=NP$.

The strict inequalities matter: a theorem excluding ratios above $r$ does not automatically exclude the boundary ratio $r$. Likewise, this argument concerns deterministic polynomial-time guarantees; hardness against randomised algorithms needs an appropriate randomised complexity assumption.

Example

MaxE3SAT to Max2SAT

The ten-clause reduction replaces each three-literal source clause by a group of ten clauses of length at most two. After choosing each auxiliary variable optimally, the group contributes $6$ satisfied clauses plus $1$ if the original clause is satisfied.

For $m$ source clauses, the target optimum is therefore

$$O_2=6m+O_1.$$

Since $O_1\ge 7m/8$, we obtain $O_2\le (55/7)O_1$. The backward conversion does not increase absolute error, giving

$$\alpha =\frac{55}{7},\beta =1.$$

Thus a target ratio $\rho$ yields a source ratio $1-(55/7)(1-\rho )$. The linked construction proves both bounds and explains why arbitrary target assignments are covered.