L-reduction

In computer science, particularly the study of approximation algorithms, an L-reduction ("linear reduction") is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preserving reduction. L-reductions in studies of approximability of optimization problems play a similar role to that of polynomial reductions in the studies of computational complexity of decision problems.

The term L reduction is sometimes used to refer to log-space reductions, by analogy with the complexity class L, but this is a different concept.

Before giving the definition, we recall some concepts of optimization problems, illustrated with the travelling salesman problem (TSP). First an instance is the input of the problem, i.e. the information we need to compute a solution. An instance for TSP is a finite set of cities and the distances between them. A solution is a tour that visits all the cities. In the case of TSP, the cost of a solution is the length of the tour. We write ${\displaystyle \mathrm {OPT_{TSP}} (x)}$ to be the cost of an optimal solution, i.e. the length of a shortest tour. Let A and B be optimization problems and c_A and c_B their respective cost functions.

A pair of functions f and g is an L-reduction if all of the following conditions are met:

• functions f and g are computable in polynomial time,
• if x is an instance of problem A, then f(x) is an instance of problem B,
• if y' is a solution to f(x), then g(y' ) is a solution to x,
• there exists a positive constant α such that

${\displaystyle \mathrm {OPT_{B}} (f(x))\leq \alpha \mathrm {OPT_{A}} (x)}$,

• there exists a positive constant β such that for every solution y' to f(x)

${\displaystyle |\mathrm {OPT_{A}} (x)-c_{A}(g(y'))|\leq \beta |\mathrm {OPT_{B}} (f(x))-c_{B}(y')|}$.

Here is a L-reduction from MAX 3-SAT to MAX 2-SAT.¹ Consider a MAX 3-SAT instance ${\displaystyle \varphi :=\bigwedge _{i=1}^{m}(\ell _{i}^{1}\lor \ell _{i}^{2}\lor \ell _{i}^{3})}$ where ${\displaystyle \ell _{i}^{1}}$, ${\displaystyle \ell _{i}^{2}}$and ${\displaystyle \ell _{i}^{3}}$are literals. The function ${\displaystyle f}$ of our L-reduction is defined as follows. The MAX 2-SAT instance ${\displaystyle f(\varphi )}$ is the formula:

${\displaystyle f(\varphi ):=\bigwedge _{i=1}^{m}(\ell _{i}^{1}\land \ell _{i}^{2}\land \ell _{i}^{3}\land \ell _{i}^{4}\land ({\bar {\ell }}_{i}^{1}\lor {\bar {\ell }}_{i}^{2})\land ({\bar {\ell }}_{i}^{1}\lor {\bar {\ell }}_{i}^{3})\land ({\bar {\ell }}_{i}^{2}\lor {\bar {\ell }}_{i}^{3})\land (\ell _{i}^{1}\lor {\bar {\ell }}_{i}^{3})\land (\ell _{i}^{2}\lor {\bar {\ell }}_{i}^{4})\land ({\bar {\ell }}_{i}^{3}\lor {\bar {\ell }}_{i}^{4})}$ where ${\displaystyle \ell _{i}^{4}}$ is a new variable.

The function ${\displaystyle g}$ of our L-reduction is defined as follows. Given an assignment ${\displaystyle \nu }$ for ${\displaystyle f(\varphi )}$, we define ${\displaystyle g(\nu )}$ to be the assignment ${\displaystyle \nu }$ restricted to variables in ${\displaystyle \varphi }$ (i.e. we just ignore the truths of the variables ${\displaystyle \ell _{i}^{4}}$). We can prove that:

• ${\displaystyle \mathrm {OPT_{MAX-2SAT}} (f(\varphi ))\leq 13\mathrm {OPT_{MAX-3SAT}} (\varphi )}$;
• ${\displaystyle |\mathrm {OPT_{MAX3SAT}} (\phi )-c_{MAX3SAT}(g(\nu '))|\leq |\mathrm {OPT_{MAX-2SAT}} (f(\phi ))-c_{MAX-2SAT}(y')|}$.

An L-reduction from problem A to problem B implies an AP-reduction when A and B are minimization problems and a PTAS reduction when A and B are maximization problems. In both cases, when B has a PTAS and there is an L-reduction from A to B, then A also has a PTAS.²³ This enables the use of L-reduction as a replacement for showing the existence of a PTAS-reduction; Crescenzi has suggested that the more natural formulation of L-reduction is actually more useful in many cases due to ease of usage.⁴

Let the approximation ratio of B be ${\displaystyle 1+\delta }$. Begin with the approximation ratio of A, ${\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}}$. We can remove absolute values around the third condition of the L-reduction definition since we know A and B are minimization problems. Substitute that condition to obtain

${\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\leq {\frac {\mathrm {OPT} _{A}(x)+\beta (c_{B}(y')-\mathrm {OPT} _{B}(x'))}{\mathrm {OPT} _{A}(x)}}}$

Simplifying, and substituting the first condition, we have

${\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\leq 1+\alpha \beta \left({\frac {c_{B}(y')-\mathrm {OPT} _{B}(x')}{\mathrm {OPT} _{B}(x')}}\right)}$

But the term in parentheses on the right-hand side actually equals ${\displaystyle \delta }$. Thus, the approximation ratio of A is ${\displaystyle 1+\alpha \beta \delta }$.

This meets the conditions for AP-reduction.

Let the approximation ratio of B be ${\displaystyle {\frac {1}{1-\delta '}}}$. Begin with the approximation ratio of A, ${\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}}$. We can remove absolute values around the third condition of the L-reduction definition since we know A and B are maximization problems. Substitute that condition to obtain

${\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\geq {\frac {\mathrm {OPT} _{A}(x)-\beta (c_{B}(y')-\mathrm {OPT} _{B}(x'))}{\mathrm {OPT} _{A}(x)}}}$

Simplifying, and substituting the first condition, we have

${\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\geq 1-\alpha \beta \left({\frac {c_{B}(y')-\mathrm {OPT} _{B}(x')}{\mathrm {OPT} _{B}(x')}}\right)}$

But the term in parentheses on the right-hand side actually equals ${\displaystyle \delta '}$. Thus, the approximation ratio of A is ${\displaystyle {\frac {1}{1-\alpha \beta \delta '}}}$.

If ${\displaystyle {\frac {1}{1-\alpha \beta \delta '}}=1+\epsilon }$, then ${\displaystyle {\frac {1}{1-\delta '}}=1+{\frac {\epsilon }{\alpha \beta (1+\epsilon )-\epsilon }}}$, which meets the requirements for PTAS reduction but not AP-reduction.

L-reductions also imply P-reduction.⁴ One may deduce that L-reductions imply PTAS reductions from this fact and the fact that P-reductions imply PTAS reductions.

L-reductions preserve membership in APX for the minimizing case only, as a result of implying AP-reductions.

• Dominating set: an example with α = β = 1
• Token reconfiguration: an example with α = 1/5, β = 2