Complete uniform gap-preserving CSP reductions

Throughout this page a binary constraint graph is one in the convention of Constraint graph and labeling value: a finite ordinary undirected multigraph with paired incidence slots, a finite nonempty alphabet $\mathrm{\Sigma }$, one relation $R_e\subseteq {\mathrm{\Sigma }}^2$ per edge in a specified endpoint order, and explicit Boolean relation tables. For an edge set $E\mathrm{\ne }\mathrm{\varnothing }$ the value ${\mathrm{val}}_{\sigma }(G)$ is the fraction of ordinary edges satisfied by the labeling $\sigma$, and $\mathrm{UNSAT}(G)={\min }_{\sigma }(1-{\mathrm{val}}_{\sigma }(G))$; an edgeless graph has value one and unsatisfiability zero, as in the published convention. The explicit encoding of $G$ is the list of vertices, the paired incidence slots, the alphabet size and the relation tables; its bit length is the input size of the algorithms below.

Fix an alphabet-size parameter $s\ge 1$ and a degree parameter $d\ge 1$ for the input graphs. A complete uniform gap-preserving reduction with output alphabet ${\mathrm{\Sigma }}^{\mathrm{\prime }}$, output degree bound $d^{\mathrm{\prime }}$, blowup $C$ and gap map $g$ consists of a deterministic algorithm $R$ that, given the explicit encoding of a binary constraint graph $G$ over an alphabet $\mathrm{\Sigma }$ with $\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }=s$ whose underlying graph has all vertex degrees at most $d$, outputs the explicit encoding of a binary constraint graph $R(G)$ over the fixed alphabet ${\mathrm{\Sigma }}^{\mathrm{\prime }}$ such that:

1. Output shape. Arity stays two, all vertex degrees of $R(G)$ are at most $d^{\mathrm{\prime }}$, and $\mathrm{\mid }E(R(G))\mathrm{\mid }\le C\mathrm{\mid }E(G)\mathrm{\mid },\mathrm{\mid }V(R(G))\mathrm{\mid }\le C\mathrm{\mid }E(G)\mathrm{\mid }\text{ whenever }E(G)\mathrm{\ne }\mathrm{\varnothing }\mathrm{.}$ An edgeless input is mapped to an edgeless output, which therefore has value one.
2. Completeness. $\mathrm{UNSAT}(G)=0$ implies $\mathrm{UNSAT}(R(G))=0$.
3. Gap preservation. $\mathrm{UNSAT}(R(G))\ge g(\mathrm{UNSAT}(G))$ for every input $G$, where $g:[0,1]\to [0,1]$ is nondecreasing with $g(0)=0$ and $g(\epsilon )>0$ for every $\epsilon >0$.
4. Uniformity. $R$ runs in time polynomial in the bit length of the explicit input encoding, and the output is explicit. The alphabet ${\mathrm{\Sigma }}^{\mathrm{\prime }}$, the numbers $d^{\mathrm{\prime }}$, $C$ and the function $g$ depend only on the fixed parameters $s,d$ and on $R$ itself, never on $\mathrm{\mid }V(G)\mathrm{\mid }$ or $\mathrm{\mid }E(G)\mathrm{\mid }$.

The definition asserts no existence statement: it records the interface in which the degree-reduction, powering and assignment-tester steps of this page are stated. Isolated vertices may be deleted from inputs and outputs without changing value or unsatisfiability, so the vertex bound in clause 1 is never needed for padded inputs; the bounded-degree clause and the fixed alphabet keep the explicit encoding length of the output within a constant multiple of $\mathrm{\mid }V(R(G))\mathrm{\mid }+\mathrm{\mid }E(R(G))\mathrm{\mid }$ plus logarithmic vertex names. Loops count as ordinary edges with two incidences and a relation tested on the repeated label, exactly as published. Monotonicity of $g$ is used only to compose gap maps, in Complete linear-blowup reductions compose, never to enlarge an input hypothesis.