An ordinary reduction takes a SAT formula and constructs a graph and a bound . The reduction does not find a vertex cover. Instead, it guarantees that is satisfiable exactly when has a vertex cover of size at most . Here means the number of vertices in a smallest cover of the constructed graph; can depend on .
Why is versus not enough for approximation hardness? At an illustrative threshold , a factor- algorithm may return a cover of size when the optimum is ; it could also return a cover of size when the optimum is . Its output does not distinguish the two cases. Suppose a gap-introducing reduction instead promised, for every formula with its own threshold , that satisfiable gives , while unsatisfiable gives . If happens to be , the two ranges are and . Each separate edge below needs one cover vertex (orange). These graphs illustrate the counts; they are not the output of a SAT reduction.
Now inspect the size of the feasible cover returned by a hypothetical factor- algorithm. On a satisfiable formula, . On an unsatisfiable formula, every feasible cover satisfies . Testing would therefore decide SAT; the threshold is in the pictured numerical illustration. The gap is valuable because the algorithm’s allowed error cannot cross this threshold.