Gap reduction

In computational complexity theory, a gap reduction is a reduction to a particular type of decision problem, known as a c-gap problem. Such reductions provide information about the hardness of approximating solutions to optimization problems.

c-gap problem

We define a c-gap problem as follows: given an optimization (maximization or minimization) problem P, the equivalent c-gap problem distinguishes between two cases, for an input k:

OPT ≤ k (YES instance)

OPT > c⋅k (NO instance)

The value c does not need to be constant; it can depend on the size of the instance of P. Note that if c-approximating the solution to an instance of P is at least as hard as solving the c-gap version of P.

A simple example of a c-gap problem is the nonmetric Traveling Salesman problem. We can reduce from the Hamiltonian path problem on a given graph G = (V, E) to this problem as follows: we construct a complete graph G' = (V, E'). For each edge e ∈ G', we let w(e) = ε if e ∈ G and w(e) = 1 otherwise, for some small ε > 0. A Hamiltonian path in this graph exists if and only if there exists a traveling salesman solution with weight (|V|-1)ε. For an appropriate choice of ε, this gives an arbitrarily large finite gap between instances of the Hamiltonian Path problem that have a solution and instances that do not.

Gap-producing reduction

A gap-producing reduction is a reduction from an optimization problem to a c-gap problem: for example, Hamiltonian Path can be reduced to the nonmetric Traveling Salesman problem, as above.

Gap-preserving reduction

A gap-preserving reduction is a reduction from a c-gap problem to a c'-gap problem. More specifically, we are given an instance x of a problem A with |x| = n and want to reduce it to an instance x' of a problem B with |x'| = n'. A gap-preserving reduction from A to B is a set of functions (k(n), k'(n'), c(n), c'(n')) such that

For minimization problems:

OPT_A(x) ≤ k ⇒ OPT_B(x') ≤ k', and

OPT_A(x) ≥ c⋅k ⇒ OPT_B(x') ≥ c'⋅k'

For maximization problems:

OPT_A(x) ≥ k ⇒ OPT_B(x') ≥ k', and

OPT_A(x) ≤ k/c ⇒ OPT_B(x') ≤ k'/c'

If c' > c, then this is a gap-amplifying reduction.

Examples

Max E3SAT

This problem is a form of the Boolean satisfiability problem (SAT), where each clause contains three distinct literals and we want to maximize the number of clauses satisfied.

Håstad showed that the (1/2+ε, 1-ε)-gap version of a similar problem, MAX E3-X(N)OR-SAT, is NP-hard. The MAX E3-X(N)OR-SAT problem is a form of SAT where each clause is the XOR of three distinct literals, exactly one of which is negated. We can reduce from MAX E3-X(N)OR-SAT to MAX E3SAT as follows:

A clause x_i ⊕ x_j ⊕ x_k = 0 is converted to (x_i ∨ x_j ∨ x_k) ∧ (¬x_i ∨ ¬x_j ∨ x_k) ∧ (¬x_i ∨ x_j ∨ ¬x_k) ∧ (x_i ∨ ¬x_j ∨ ¬x_k)

A clause x_i ⊕ x_j ⊕ x_k = 0 is converted to (¬x_i ∨ ¬x_j ∨ ¬x_k) ∧ (¬x_i ∨ x_j ∨ x_k) ∧ (x_i ∨ ¬x_j ∨ x_k) ∧ (x_i ∨ x_j ∨ ¬x_k)

If a clause is not satisfied in the original instance of MAX E3-X(N)OR-SAT, then at most three of the four corresponding clauses in our MAX E3SAT instance can be satisfied. Using a gap argument, it follows that a YES instance of the problem has at least a (1-ε) fraction of the clauses satisfied, while a NO instance of the problem has at most a (1/2+ε)(1) + (1/2-ε)(3/4) = (7/8 + ε/4)-fraction of the clauses satisfied. Thus, it follows that (7/8 + ε, 1 - ε)-gap MAX E3SAT is NP-hard. Note that this bound is tight, as a random assignment of variables gives an expected 7/8 fraction of satisfied clauses.

Label Cover

The label cover problem is defined as follows: given a bipartite graph G = (A∪B, E), with

A = A₁ ∪ A₂ ∪ ... ∪ A_k, |A| = n, and |A_i| = n/k

B = B₁ ∪ B₂ ∪ ... ∪ B_k, |B| = n, and |B_i| = n/k

We define a "superedge" between A_i and B_j if at least one edge exists from A_i to B_j in G, and define the superedge to be covered if at least one edge from A_i to B_j is covered.

In the max-rep version of the problem, we are allowed to choose one vertex from each A_i and each B_i, and we aim to maximize the number of covered superedges. In the min-rep version, we are required to cover every superedge in the graph, and want to minimize the number of vertices we choose. Manurangsi and Moshkovitz show that the (O(n^1/4), 1)-gap version of both problems is solvable in polynomial time.

See also

• Approximation-preserving reduction
• PTAS reduction