APX-Hard Problems, in depth: the approximation ladder, L-reductions, APX-completeness, a tested reduction chain and what hardness changes

Ratios and the class ladder

An NP optimisation problem has instances, feasible solutions checkable in polynomial time, and a cost to minimise or maximise. For an algorithm that returns a solution of cost c on an instance with optimum OPT, define the ratio as max(c/OPT, OPT/c), so it is always at least 1 for minimisation and maximisation alike. An r-approximation has ratio at most r on every instance. Some papers quote maximisation ratios as fractions below 1 (for example 7/8 for MAX-3SAT); 7/8 in that convention is 8/7 in this one.

The classes form a ladder, shown below. Each inclusion is strict if P ≠ NP, and the witnesses are concrete problems: knapsack has an FPTAS but is NP-hard, Euclidean TSP has a PTAS (Arora, 1998) but no FPTAS, vertex cover is in APX but has no PTAS, set cover is approximable within ln n but no constant, and maximum independent set cannot be approximated within n^1-ε.

Reductions that preserve approximation

Karp reductions, the tool for NP-completeness, map yes-instances to yes-instances. They say nothing about near-optimal solutions. The textbook example: a set S is a vertex cover exactly when its complement is an independent set, so the two problems are equivalent for exact solution. Yet vertex cover has a simple 2-approximation and independent set has no constant-ratio approximation at all. In a graph of n vertices with a perfect matching and an optimal cover of n/2, taking every vertex is a cover within factor 2, and its complement is an independent set of size 0.

Transferring approximation needs a reduction that also maps solutions back and bounds how much quality is lost. The classic is the L-reduction of Papadimitriou and Yannakakis (1991), a pair of polynomial-time maps f and g with constants α, β > 0:

1. f maps an instance x of A to an instance f(x) of B with OPT_B(f(x)) ≤ α · OPT_A(x).
2. g maps any solution y of f(x) to a solution g(y) of x with |OPT_A(x) - c_A(g(y))| ≤ β · |OPT_B(f(x)) - c_B(y)|.

Condition 1 says the optimum does not blow up; condition 2 says the absolute loss does not blow up. Together, a solution with relative error ε on B maps to one with relative error at most αβε on A, so a PTAS for B would yield a PTAS for A. Later work introduced looser variants: PTAS-reductions only require that any approximation scheme for B gives one for A, and AP-reductions (Crescenzi and co-authors) are a variant with a linear relationship between the ratios. Each class definition says which reduction it uses, and the results are not interchangeable, so a careful statement always names it.

With these in hand: a problem is APX-hard if every problem in APX reduces to it under PTAS-reductions (or AP-reductions, depending on the source), and APX-complete if it is also in APX. MAX-3SAT is the canonical APX-complete problem: the PCP theorem gives it a constant inapproximability gap, and 1990s work by Khanna, Motwani, Sudan and Vazirani showed that, for polynomially bounded problems, APX is the closure of the syntactic class MAX SNP under approximation-preserving reductions. To show a new problem APX-hard you do not repeat any of that: you build one L-reduction (or PTAS-reduction) from a known APX-hard problem, exactly as you use a single Karp reduction for NP-hardness.

A worked chain: MAX-3SAT-B to vertex cover

Here is a complete chain, small enough to test. Start from MAX-3SAT-B: MAX-3SAT where each variable occurs at most B times, for a fixed constant B. It is known to be APX-complete for suitable B, and the bound is what keeps degrees constant below. The reduction to maximum independent set builds one vertex per literal occurrence, joins the three vertices of each clause into a triangle, and joins every occurrence of x to every occurrence of not-x:

def max3sat_to_mis(clauses):
    """Vertices = literal occurrences. Triangle per clause; edge between x and -x."""
    V = [(ci, lit) for ci, cl in enumerate(clauses) for lit in cl]
    E = {(i, j) for i, (ci, li) in enumerate(V) for j, (cj, lj) in enumerate(V)
         if i < j and (ci == cj or li == -lj)}
    return V, E

def is_to_assignment(V, S, n):
    """Map an independent set back: make every chosen literal true."""
    x = [False] * n
    for idx in S:
        _, lit = V[idx]
        x[abs(lit) - 1] = lit > 0
    return x

An independent set takes at most one vertex per triangle and never both x and not-x, so its chosen literals can all be made true at once, satisfying at least |S| clauses. Conversely, a truth assignment that satisfies k clauses gives an independent set of size k by picking one true literal per satisfied clause. So the optima are equal and g loses nothing beyond what the independent set lost: α = β = 1. A brute-force check over 300 random formulas (3 to 8 variables, 3 to 12 clauses) found zero cases where the maximum number of satisfied clauses differed from the maximum independent set. On the four-clause formula (x1 ∨ x2 ∨ x3), (¬x1 ∨ ¬x2 ∨ x3), (¬x1 ∨ x2 ∨ ¬x3), (x1 ∨ ¬x2 ∨ ¬x3), the graph has 12 vertices and 24 edges, and both optima are 4.

The degree bound is where B matters. A vertex for an occurrence of x touches two clause-mates and at most B - 1 occurrences of not-x, so the degree is at most B + 1. This proves independent set is APX-hard on graphs of bounded degree, where it is also in APX (greedy achieves a ratio depending only on the degree). Do not read it as a statement about general graphs, where independent set is far harder and not in APX.

Next, bounded-degree vertex cover. Take the same graph and complement the set. In a graph with n vertices and maximum degree Δ, every maximal independent set has at least n/(Δ + 1) vertices, so OPT_VC ≤ n ≤ (Δ + 1) OPT_IS: condition 1 holds with α = Δ + 1. A cover worse than optimal by k vertices complements to an independent set worse by exactly k, so β = 1. The reduction that failed for general graphs works here because bounded degree keeps the optima within a constant factor of each other.

The catalogue and its constants

The table lists the problems you are most likely to meet, the best simple guarantee, and the best NP-hardness bound in ratio form. Unique Games Conjecture (UGC) bounds are conditional on an unproven conjecture.

Before the 2018 result, the best unconditional vertex cover bound was Dinur and Safra's 1.3606, which you will still see quoted. Bin packing is the warning case: no algorithm can guarantee better than 3/2 of the optimal number of bins, because deciding whether two bins suffice is Partition, yet algorithms exist that use (1 + ε) OPT + 1 bins. A ratio lower bound driven by tiny optima can coexist with near-optimal behaviour on every large instance.

What the label changes in practice

Hardness bounds are worst-case statements. A quick measurement shows the gap between guarantee and typical behaviour. The maximal-matching 2-approximation for vertex cover, run on 200 random graphs with 24 vertices and edge probability 0.15 and compared with the exact optimum, averaged ratio 1.536, ranged from 1.143 to 2.000, and hit exactly 2 on a graph of 10 disjoint edges (20 vertices taken, optimum 10). The guarantee is tight and matters, but it is not the number your users will see.

What APX-hardness should change in your engineering:

• Stop searching for a scheme. If your problem L-reduces from MAX-3SAT-B or vertex cover, no algorithm will promise 1 + ε for every ε. Spend the effort elsewhere.
• Check whether your instances are a special case. Hardness proofs build awkward instances. Planar graphs admit PTASs for independent set and vertex cover (Baker's technique), Euclidean TSP has a PTAS, and bounded treewidth often allows exact dynamic programming. The real input may sit in an easy class.
• Use exact solvers with certified gaps. Integer programming solvers report a lower bound alongside the incumbent, so every answer carries a per-instance guarantee that is usually far better than the worst-case ratio. On moderate sizes they often prove optimality.
• Combine a guaranteed algorithm with local search. Run the constant-ratio algorithm first for a safe answer, then improve it, and report the better result against an LP or matching lower bound.
• Parameterise. If the optimum is small, fixed-parameter algorithms such as vertex cover kernels solve exactly in time exponential only in the solution size.

Common misreadings

Misreadings that cause real mistakes:

• "APX-hard means not approximable." Every APX-complete problem has a constant-factor algorithm; hardness only rules out arbitrarily good ones.
• "APX-hard means no ratio better than the known algorithm." For vertex cover there is a gap between 2 and √2 that is open without UGC.
• Using a Karp reduction to claim APX-hardness. The reduction must map solutions back and bound the loss; vertex cover and independent set show why.
• Dropping the degree bound. The chain above proves hardness for bounded-degree graphs. Hardness results for restricted inputs imply hardness for general inputs, not the other way round.
• Forgetting the assumption. Every bound here assumes P ≠ NP, and the UGC rows assume more.

What to do next

1. For your problem, write down the ratio convention and find the best known algorithm and hardness bound; check which reduction type the hardness uses.
2. Run the reduction code above with a brute-force check, then try building an L-reduction from vertex cover or MAX-3SAT-B to your own problem.
3. Implement the matching-based cover and the LP rounding from the vertex cover article, and measure both against an exact solver on your data.
4. Read the approximation algorithms overview and the PTAS and FPTAS article to see the rings of the ladder from the algorithm side.
5. If the class says log-APX, start from greedy set cover and its H(n) bound.