L-Reduction

Transfer approximation guarantees and hardness between optimization problems through polynomial instance and solution maps whose two fixed-constant inequalities control optimum scale and solution-error distortion.

Version

v2 · 2026-09-19 · History

Domain-specific #

2149

Domain group

Applied Sciences & Engineering

Origin domain

Computer Science & Software Engineering

Subdomains

Theoretical Computer Science, Approximation Complexity → Computer Science & Software Engineering

Aliases

L-reduction, Linear reduction

Core Idea

An L-reduction is an approximation-preserving reduction from one optimization problem A to another optimization problem B. It does more than translate instances in polynomial time. It also translates feasible solutions back and places fixed linear bounds on two quantities that ordinary decision-problem reductions do not control: the scale of the target optimum and the distortion of a solution's distance from optimum. Papadimitriou and Yannakakis introduced the construction while developing the classes MAX NP and MAX SNP; its purpose was to make completeness and hardness results preserve approximability rather than mere yes/no solvability.

How would you explain it like I'm…

Puzzle Swap, Still Close

Imagine you have a hard puzzle, and you know how to turn it into a different puzzle. You solve the new puzzle, then turn the answer back into an answer for the first one. An L-Reduction is a careful way of doing this so that if your answer to the new puzzle is pretty close to best, your answer to the old puzzle is pretty close to best too.

Close-Answer-Keeping Conversion

Some problems ask for the best answer, like the shortest route or the biggest group. Often the best is too hard to find, so we settle for 'pretty good.' An L-reduction is a recipe that changes problem A into problem B, and changes any answer to B back into an answer to A. It also makes two promises: B's best score won't be wildly bigger than A's, and if your B answer is a little off from the best, your A answer will be only a little off too. That way 'pretty good' stays 'pretty good' when you switch problems.

Approximation-Preserving Reduction

An L-Reduction connects two optimization problems A and B in a way that preserves how well they can be approximated, not just whether they can be solved. It has a fast (polynomial-time) map f turning an A-instance into a B-instance, and a map g turning any valid B-solution back into a valid A-solution. Two linear limits are required: B's optimum is at most α times A's optimum, and the gap between A's optimum and the recovered solution is at most β times the gap in B. Ordinary reductions for yes/no problems don't control these gaps at all. Because of this, approximation algorithms for B carry over to A, and hardness of approximating A transfers to B, with the product αβ controlling how much the guarantee worsens. It was introduced by Papadimitriou and Yannakakis to study the classes MAX NP and MAX SNP.

 

An L-reduction from optimization problem A to optimization problem B is an approximation-preserving reduction, introduced by Papadimitriou and Yannakakis in developing MAX NP and MAX SNP. It consists of polynomial-time maps f and g and constants α, β > 0 such that: f(x) is a B-instance; for every feasible solution y' of f(x), g(x, y') is a feasible A-solution; OPT_B(f(x)) ≤ α·OPT_A(x); and |OPT_A(x) − m_A(x, g(x, y'))| ≤ β·|OPT_B(f(x)) − m_B(f(x), y')|. The first inequality stops the target optimum from blowing up relative to the source, and the second stops target error from becoming disproportionately large source error. The reduction is directional: to show B is hard to approximate, reduce a known-hard A to B; conversely, an approximation algorithm for B composed with f and g approximates A. The product αβ governs degradation: for maximization, a ratio r on B gives at least (1 − αβ(1 − r))·OPT_A; for minimization, a ratio r ≥ 1 gives at most 1 + αβ(r − 1).

Scope of Application

L-reductions live inside the theory of approximation algorithms and hardness of approximation. Their scope is bounded by problems that have feasible solutions, objective values, and meaningful optima whose gaps can be compared.

• MAX SNP and APX hardness. The construction was introduced to support completeness results for bounded-error optimization classes and to let inapproximability move from established complete problems to new targets.
• Graph optimization. Problems including independent set, bounded-degree vertex cover, and Steiner tree admit gadget transformations in which an objective contribution can be tracked closely enough to prove the two inequalities; this is a non-exhaustive list.

Clarity

L-reduction turns the vague phrase “this reduction preserves approximation” into two separate audit questions. First, did the transformation keep the target optimum on the same constant scale as the source optimum? Second, does every unit of target suboptimality create at most a fixed number of units of source suboptimality? Those questions isolate two failure modes that are otherwise easy to conflate.

Manages Complexity

An inapproximability proof could compare every possible target solution with every recovered source solution and derive a fresh ratio bound for each construction. L-reduction compresses that proof burden into four reusable obligations. Once polynomial computability and feasibility are established, all numerical behavior is summarized by alpha and beta. The rest of the approximation transfer follows algebraically.

Abstract Reasoning

L-reduction supports three recurring proof moves.

Constructive transfer. Given an approximation procedure for B, compute f(x), run the procedure, and apply g. The inequalities transform a target guarantee into a source guarantee. This is the positive, algorithmic reading of the reduction.

Contrapositive hardness. Suppose a target approximation of some quality would induce, through the same bounds, a source approximation ruled out by a known theorem.

Knowledge Transfer

Within approximation complexity, the L-reduction transfers literally. The same roles recur when the source is a satisfiability problem and the target a graph problem, when both problems are graph optimizations, or when the target is a network-design problem: instance map, back-map, optimum-scale bound, error-gap bound, and approximation consequence. The vocabulary changes only at the level of what counts as a feasible solution and an objective unit.

Relationships to Other Abstractions

Current abstraction L-Reduction Domain-specific

Parents (2) — outgoing typed relations

• L-Reduction is a kind of Transformation Prime

  L-reduction instantiates prime:transformation.

• L-Reduction presupposes Approximation Prime

  L-reduction instantiates prime:transformation.

Hierarchy paths (2) — routes to 2 parentless roots

• L-Reduction → is a kind of Transformation → is a kind of, typical Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space

L-Reduction sits in a sparse region of the domain-specific corpus (71^st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

• PTAS Reduction — 0.91
• Interior-Point Method — 0.84
• Constrained optimization — 0.83
• Approximation Algorithm — 0.82
• Optimal Substructure — 0.82

Computed from structural-signature embeddings · 2026-10-25