Approximation Algorithms and Gap Reductions

Consider the following deterministic procedure: list the edges of $G$ in the fixed order, start with $M=\mathrm{\varnothing }$, and scan the list once, adding the current edge to $M$ when neither of its endpoints is already $M$-saturated; at the end return $M$ and the set $C$ of all endpoints of edges of $M$. Each step inspects two saturation marks and possibly sets two of them, so the procedure runs in time polynomial in the encoded size of $G$, and the fixed edge order is its tie rule.

One has $\mathrm{\mid }M\mathrm{\mid }\le {\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}$. Let $C^{\ast }$ be a vertex cover with $\mathrm{\mid }{C}^{\ast }\mathrm{\mid }={\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}$. Each edge of $M$ has at least one endpoint in $C^{\ast }$; assign to it such an endpoint explicitly: the smaller of its two endpoints in the fixed vertex order if that endpoint lies in $C^{\ast }$, and otherwise its other endpoint. Distinct edges of $M$ are vertex-disjoint, so distinct edges receive distinct vertices of $C^{\ast }$; the assignment is therefore an injection of $M$ into $C^{\ast }$, and $\mathrm{\mid }M\mathrm{\mid }\le \mathrm{\mid }{C}^{\ast }\mathrm{\mid }={\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}$.

Since $M$ is a matching, its edges are pairwise disjoint, so the $2\mathrm{\mid }M\mathrm{\mid }$ endpoints of its edges are distinct vertices and $\mathrm{\mid }C\mathrm{\mid }=2\mathrm{\mid }M\mathrm{\mid }$. Every vertex of $C$ is $M$-saturated by construction.

The matching $M$ is maximal. Indeed, suppose an edge $e$ of $G$ had both endpoints not in $C$, that is, both $M$-exposed at the end of the scan. A vertex once marked saturated is never unmarked, so both endpoints were still exposed when $e$ was scanned; the procedure would then have added $e$ to $M$, a contradiction. Hence no edge can be added to $M$, and $M$ is maximal.

If $G$ has no edges, the scan adds nothing, so $M=\mathrm{\varnothing }$ and $C=\mathrm{\varnothing }$; the empty set is a vertex cover and no nonempty set is needed, so ${\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}=0=\mathrm{\mid }C\mathrm{\mid }=2\mathrm{\mid }M\mathrm{\mid }$, and both sides of the displayed bound are zero.

The set $C$ is a vertex cover: if some edge $e$ of $G$ had both endpoints outside $C$, then $M\cup \{e\}$ would be a matching strictly larger than $M$, contradicting maximality. Hence every edge meets $C$, so $C$ is a vertex cover and ${\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}\le \mathrm{\mid }C\mathrm{\mid }$.

Combining steps 2.1, 3.1 and 1.2, $\mathrm{\mid }C\mathrm{\mid }=2\mathrm{\mid }M\mathrm{\mid }\le 2{\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}$ and $C$ is a vertex cover computed by the deterministic polynomial-time procedure of step 1.1. By [F4] the procedure is a $2$-approximation for the minimum vertex cover problem.

For every finite simple graph, a maximal matching is produced in deterministic polynomial time after the tie rule of step 1.1 is fixed, its endpoint set is a vertex cover $C$ with $\mathrm{\mid }C\mathrm{\mid }=2\mathrm{\mid }M\mathrm{\mid }\le 2{\mathrm{OPT}}_{\mathrm{V}\mathrm{C}}$, and the edgeless case is covered by step 2.3.

Fix a step of the greedy run, let $R$ be the set of elements still uncovered just before it and $r=\mathrm{\mid }R\mathrm{\mid }\ge 1$ the remaining count; let $N\subseteq R$, $N\mathrm{\ne }\mathrm{\varnothing }$, be the set of elements newly covered by the set chosen at this step, so the chosen price per newly covered element is $c\mathrm{/}\mathrm{\mid }N\mathrm{\mid }$ for that set's cost $c$. Put $t_S=\mathrm{\mid }S\cap R\mathrm{\mid }$ for every set $S$ of the fixed minimum-cost cover $O^{\ast }$ of [F2]. Since $O^{\ast }$ covers $U$ and hence $R$, every element of $R$ lies in at least one $S\in O^{\ast }$; summing the counts $t_S$ therefore counts each element of $R$ at least once, so ${\sum }_{S\in O^{\ast }}{t}_S\ge r\ge 1$.

Let $T=\{S\in O^{\ast }:t_S>0\}$. Then $T$ is nonempty because ${\sum }_{S\in O^{\ast }}{t}_S\ge r\ge 1$, and ${\sum }_{S\in T}{t}_S={\sum }_{S\in O^{\ast }}{t}_S\ge r>0$, while ${\sum }_{S\in T}c(S)\le {\sum }_{S\in O^{\ast }}c(S)=\mathrm{O}\mathrm{P}\mathrm{T}$ because all costs are nonnegative and $T\subseteq O^{\ast }$. The $t_S$-weighted average of the ratios $c(S)\mathrm{/}{t}_S$ over $S\in T$ equals $({\sum }_{S\in T}c(S))/\left({\sum }_{S\in T}{t}_S\right)$ and is therefore at least the minimum of those ratios, so that minimum is at most $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}r$.

Each $S\in T$ is a listed set of the instance and has positive newly covered count $t_S>0$ at this step, so it is a candidate in the greedy choice; by [F1] the chosen set minimizes the ratio among all candidates, so the chosen price per newly covered element satisfies $c\mathrm{/}\mathrm{\mid }N\mathrm{\mid }\le {\min }_{S\in T}c(S)\mathrm{/}{t}_S\le \mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}r$. Every element newly covered at this step receives the charge $c\mathrm{/}\mathrm{\mid }N\mathrm{\mid }$, hence a charge of at most $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}r$.

Order the elements of $U$ by the round in which they are first covered, breaking ties within a round by the fixed order of $U$, and let $u$ be the $j$-th element of this order, covered in a round that begins with $r$ uncovered elements. Before that round exactly $n-r$ elements are already covered, all of them earlier than $u$ in the order, so $j\ge n-r+1$, that is, $r\ge n-j+1\ge 1$; since the charge of $u$ is at most $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}r$ by step 3.1 and $r\ge n-j+1>0$, it is at most $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}(n-j+1)$.

Consequently the price chosen in any greedy step with $r\ge 1$ uncovered elements is at most $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}r$, and the $j$-th element in first-coverage order receives charge at most $\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}(n-j+1)$ for every $j=1,\dots ,n$; both bounds are ordinary inequalities of nonnegative rationals with positive denominators, so no division by zero occurs.

Each round of the greedy algorithm covers at least one element that was uncovered before it, because the chosen set has positive newly covered count; hence after at most $n$ rounds the set of uncovered elements is empty, the algorithm halts, and the chosen list is a feasible cover of $U$. The total cost of the chosen cover equals the sum of the charges of all elements, since each chosen set's cost is divided equally among exactly the elements that it newly covers, and every element is newly covered in exactly one round.

If $n=0$, that is $U=\mathrm{\varnothing }$, the algorithm returns the empty cover of cost $0$, which is feasible; every feasible cover has nonnegative cost, so $\mathrm{O}\mathrm{P}\mathrm{T}=0$, and the asserted bound reads $0\le H_0\cdot 0=0$ by [F3].

Assume $n\ge 1$ and order the elements by first coverage, breaking ties within a round by the fixed order of $U$. For the $j$-th element of this order the charging bound [F2] gives ${\text{charge}}_j\le \mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}(n-j+1)$, a valid inequality because the round of first coverage has a positive remaining count and the index satisfies $n-j+1\ge 1$.

Summing the bounds of step 2.1 over $j=1,\dots ,n$ and substituting $k=n-j+1$, the total cost of the greedy cover satisfies ${\sum }_{j=1}^n{\text{charge}}_j\le {\sum }_{j=1}^n\mathrm{O}\mathrm{P}\mathrm{T}\mathrm{/}(n-j+1)=\mathrm{O}\mathrm{P}\mathrm{T}{\sum }_{k=1}^{n}1\mathrm{/}k=H_n\mathrm{O}\mathrm{P}\mathrm{T}$ by [F3]. The total cost is the sum of the charges by step 1.1, so the greedy cover has cost at most $H_n\mathrm{O}\mathrm{P}\mathrm{T}$.

For $n\ge 1$ the algorithm returns a feasible cover of cost at most $H_n\mathrm{O}\mathrm{P}\mathrm{T}$ in deterministic polynomial time: there are at most $n$ rounds by step 1.1, each round scans the finitely many listed sets, computes exact rational ratios with positive denominators, and performs exact comparisons; for $n=0$ the bound is the zero identity of step 1.2. By [F4] the procedure is a polynomial-time $H_n$-approximation for weighted set cover.

Take one uniform two-point probability space per vertex and form their finite product; its outcomes are the maps $b:V\to \{0,1\}$ with the weights of [F2], so the bits $b_v$ are independent and each is $0$ or $1$ with probability $1\mathrm{/}2$. Interpret side $b_v$ as the side of vertex $v$; this is exactly the stated independent uniform placement.

For each edge $e=\{u,v\}$ define the indicator $X_e:={\mathbf{1}}_{b_u\mathrm{\ne }{b}_v}$ of the event that $e$ crosses the cut, and put $X:={\sum }_{e\in E}{X}_e$. At each outcome the sum counts precisely the crossing edges, so $X$ is the number of crossing edges.

Fix an edge $e=\{u,v\}$. The events $\{b_u=0\}$ and $\{b_v=1\}$ are coordinate events, so [F2] gives $\mathbb{P}[b_u=0,b_v=1]=\frac{1}{2}\cdot \frac{1}{2}=\frac{1}{4}$; similarly $\mathbb{P}[b_u=1,b_v=0]=\frac{1}{4}$. The two cases are disjoint and exhaust $\{b_u\mathrm{\ne }{b}_v\}$, hence $\mathbb{P}[b_u\mathrm{\ne }{b}_v]=\frac{1}{4}+\frac{1}{4}=\frac{1}{2}$.

By [F3] and step 2.2, $\mathbb{E}[X_e]=\mathbb{P}[b_u\mathrm{\ne }{b}_v]=\frac{1}{2}$ for every edge $e$.

If $m=0$, then $X={\sum }_{e\in \mathrm{\varnothing }}{X}_e=0$ at every outcome by the empty-sum convention of [F3], so $\mathbb{E}[X]=0=m\mathrm{/}2$; also every placement crosses all zero edges, so ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}=0$, and both values are zero.

By linearity [F4] applied to the finite family $(X_e{)}_{e\in E}$, $\mathbb{E}[X]={\sum }_{e\in E}\mathbb{E}[X_e]=m\cdot \frac{1}{2}=m\mathrm{/}2$. The calculation uses only the individual probabilities of step 3.1; no independence between distinct edge indicators is assumed or needed.

Every placement yields a cut with at most $m$ crossing edges, since $G$ has $m$ edges in total; hence ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}\le m$, and step 4.1 gives $\mathbb{E}[X]=m\mathrm{/}2\ge {\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}\mathrm{/}2$.

Consequently the independent uniform placement produces a cut whose expected number of crossing edges is $m\mathrm{/}2$, at least half of ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}$ in the value sense of [F5], with the zero-edge case covered by step 3.2.

Let $X:={\sum }_{e\in E}{X}_e$ be the number of crossing edges, where $X_e$ is the indicator that the endpoints of $e$ lie on different sides. For a partial assignment $a=(a_1,\dots ,a_k)$ of the first $k$ bits, define the conditional expectation $\mathbb{E}[X\mid a]$ as the average of $X$ over the $2^{n-k}$ equally weighted completions. The closed form is $\mathbb{E}[X\mid a]=A(a)+\frac{1}{2}B(a)$, where $A(a)$ counts the edges whose two endpoints are among the fixed vertices and which cross under $a$, and $B(a)$ counts the edges with at least one unfixed endpoint: a fully fixed edge contributes its crossing indicator, an edge with exactly one fixed endpoint crosses for exactly one of the two equally likely values of the free bit, an edge with two unfixed endpoints crosses for exactly two of the four equally likely pairs of free bits, and [F3] sums these contributions, the edges being finitely many.

For any $k<n$ and any $a$, the completions of $a$ split into those with $b_{k+1}=0$ and those with $b_{k+1}=1$, two equally weighted families of equal size, so $\mathbb{E}[X\mid a]=\frac{1}{2}(\mathbb{E}[X\mid a,0]+\mathbb{E}[X\mid a,1])$. Hence at least one of the two one-bit extensions has conditional expectation at least $\mathbb{E}[X\mid a]$, and the maximizer is at least the current value.

Define the algorithm: start with the empty assignment $a$; for $k=0,1,\dots ,n-1$ compute the two numbers $\mathbb{E}[X\mid a,0]$ and $\mathbb{E}[X\mid a,1]$ from the closed form of step 1.1, each a sum over the $m$ edges, and extend $a$ by $b_{k+1}=0$ if $\mathbb{E}[X\mid a,0]\ge \mathbb{E}[X\mid a,1]$ and by $b_{k+1}=1$ otherwise; return the resulting cut. By step 2.1 the conditional expectation does not decrease at any choice, so the nondecreasing sequence $\mathbb{E}[X\mid \mathrm{\varnothing }]=m\mathrm{/}2,\mathbb{E}[X\mid b_1],\dots ,\mathbb{E}[X\mid b_1,\dots ,b_n]=X$ ends at the actual cut size of the returned placement, giving $X\ge m\mathrm{/}2$.

The algorithm is deterministic after the fixed tie rule $b_{k+1}=0$ and the fixed vertex order, and it runs in polynomial time: $n$ rounds with two closed-form evaluations of $O(m)$ exact rational operations each, all comparisons of rationals with polynomially bounded bit lengths. By step 3.1 and [F1], the returned feasible cut satisfies $X\ge m\mathrm{/}2\ge \frac{1}{2}{\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}$; when $m=0$ both values are zero. By [F2] this is a deterministic polynomial-time $1\mathrm{/}2$-approximation for Max-Cut.

Take an optimal tour and write its cyclic ordering as $v_1,v_2,\dots ,v_n$ with the closing edge $\{v_n,v_1\}$, so ${\sum }_{i=1}^{n-1}d(v_i,v_{i+1})+d(v_n,v_1)={\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$. Delete the closing edge and let $Q$ be the subgraph of $K$ with vertex set $V$ and edge set $\{v_1{v}_2,v_2{v}_3,\dots ,v_{n-1}{v}_n\}$. The subgraph $Q$ spans $V$ and is connected: for $i<j$ the walk $v_i,v_{i-1},\dots ,v_1,v_2,\dots ,v_j$ lies in $Q$ and joins $v_i$ to $v_j$. Its total length is $w(Q)={\sum }_{i=1}^{n-1}d(v_i,v_{i+1})={\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}-d(v_n,v_1)\le {\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$, because lengths are nonnegative.

Since $Q$ is a finite connected graph, [F3] provides a spanning tree $S$ of $Q$ with $V(S)=V$ and $E(S)\subseteq E(Q)$. All lengths are nonnegative, so deleting edges cannot increase total length and $w(S)={\sum }_{e\in E(S)}d(e)\le {\sum }_{e\in E(Q)}d(e)=w(Q)\le {\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$. In particular $S$ is also a spanning tree of the complete graph $K$, since $E(S)\subseteq E(Q)\subseteq E(K)$ and $V(S)=V$.

The tree $T$ is a minimum spanning tree of the complete graph $K$, and $S$ is a spanning tree of $K$, so by [F2] $w(T)\le w(S)\le {\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$.

Therefore every metric-TSP instance satisfies $w(T)\le {\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$ for a minimum spanning tree $T$ of its complete weighted graph. The argument uses one optimal tour only as a comparison object; it computes no optimal tour and gives a lower bound on ${\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$, not an upper bound.

Form the multigraph $M$ on $V$ whose edge list contains, for each tree edge $e=\{u,v\}\in E(T)$, exactly two parallel edges between $u$ and $v$ with length $d(u,v)$; these are nonloop edges because $u\mathrm{\ne }v$. Since $T$ is connected and spanning, so is $M$; each vertex degree is ${\mathrm{deg}}_M(v)=2{\mathrm{deg}}_T(v)$, because every nonloop edge contributes one to the degree of each endpoint, hence every degree of $M$ is even; and the total length of the edge list of $M$ is ${\sum }_{e\in E(T)}2d(e)=2w(T)$.

By [F4] the multigraph $M$ has an Euler circuit $C$, which by [F3] is a closed trail using every edge of $M$ exactly once, so its total length is the total length $2w(T)$ of the edge list of $M$. Since $n\ge 3$ and the spanning tree $T$ is connected, every vertex of $T$ has degree at least one, so every vertex of $V$ occurs on $C$.

Start at the first vertex $v_0$ of $C$ and list the vertices in order of their first visit, obtaining the distinct vertices $v_0=v_{i_1},v_{i_2},\dots ,v_{i_n}$ with $\{v_{i_1},\dots ,v_{i_n}\}=V$. The closed walk $C$ splits at these first visits into $n$ consecutive segments: for $k=1,\dots ,n-1$ the segment from $v_{i_k}$ to $v_{i_{k+1}}$, and the final segment from $v_{i_n}$ back to $v_{i_1}=v_0$. These segments partition the edges of $C$, so their lengths sum to $2w(T)$.

Replace each segment by the direct edge joining its two endpoints, which exists because the graph is complete; this gives the cyclic ordering $v_{i_1},v_{i_2},\dots ,v_{i_n}$ visiting every vertex exactly once, a feasible Hamiltonian tour. Iterating the triangle inequality along a segment bounds each shortcut edge by the length of that segment, since the metric is symmetric and all lengths are nonnegative; summing over the $n$ segments gives tour cost at most the total length of $C$, namely $2w(T)$.

The construction is explicit: the doubled multigraph is read off the finitely many tree edges, its Euler circuit is obtained by the constructive direction of [F4], and the first-visit scan of the closed walk takes time linear in its length, hence polynomial time in the encoded size of the instance. Therefore first-visit shortcutting of a doubled spanning tree yields a Hamiltonian tour of cost at most $2w(T)$.

The complete graph on the vertex set of the instance, with the given lengths, is a finite connected real edge-weighted graph: the vertex set is nonempty because $n\ge 3$, and any two distinct vertices are adjacent, hence joined by the one-edge path consisting of that edge. All edge lengths are nonnegative rationals by the metric convention.

Run Kruskal's algorithm on this weighted graph, breaking ties by a fixed order of the finitely many edges. By [F4] it outputs a minimum spanning tree $T$. This run is polynomial time on the explicit rational input: there are at most $\mathrm{\mid }E\mathrm{\mid }$ additions, and each round can scan all edges, test eligibility by graph search, and compare the encoded rational lengths using polynomial bit arithmetic. By [F2], $T$ has minimum total weight among spanning trees.

Double every edge of $T$, obtaining the connected multigraph in which every vertex degree is twice its degrees in $T$, hence even; take an Euler circuit of this multigraph and shortcut repeated vertices in first-visit order. By [F6] the result is a Hamiltonian tour of the instance whose cost is at most $2w(T)$, and the doubling, traversal and first-visit scan take polynomial time in the size of the explicit graph.

The same tree $T$ is a minimum spanning tree of the complete weighted graph, so [F5] gives the lower bound $w(T)\le {\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$.

The tour returned in step 3.1 is feasible and has cost at most $2w(T)\le 2{\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$ by step 3.2. The algorithm is deterministic polynomial time by steps 2.1 and 3.1, with all ties resolved by fixed finite orders. By [F7] it is a polynomial-time $2$-approximation for metric TSP.

Fix $L\in NP$ and an input $x$ of length $n$. Under the Axiom of Choice hypothesis of [F6], [F1] supplies a verifier $V$ for $L$ with perfect completeness $c=1$, fixed soundness $s_0<1$, a bound $r(n)=O(\log n)$, a constant query bound $q$, and a fixed polynomial bound $p$ on the addressable proof length. By [F7], fix a rational $s$ with $s_0<s<1$; the verifier also has soundness at most $s$. This rational constant may be hardcoded without computing $s_0$. Put $R:=2^{r(n)}$, so $R\ge 1$ and $R$ is polynomially bounded in $n$.

For each coin string $\sigma$, the nonadaptive verifier queries a set $Q_{\sigma }$ of distinct proof locations determined by $x$ and $\sigma$, with $\mathrm{\mid }{Q}_{\sigma }\mathrm{\mid }\le q$; let $P_{\sigma }\subseteq \{0,1{\}}^{Q_{\sigma }}$ be the finite set of local assignments on which $V$ rejects, $\mathrm{\mid }{P}_{\sigma }\mathrm{\mid }\le 2^q$. If $Q_{\sigma }=\mathrm{\varnothing }$, then $P_{\sigma }$ is either empty (the verifier accepts) or the single empty assignment (the verifier rejects).

Build a CNF formula ${\mathrm{\Phi }}_x$ over one Boolean variable per addressable proof location, treating each coin string $\sigma$ in exactly one of three cases. If $P_{\sigma }=\mathrm{\varnothing }$, insert one tautology $w\vee \mathrm{\neg }w\vee w$ on a fresh bit reserved to $\sigma$. If $Q_{\sigma }=\mathrm{\varnothing }$ and the verifier rejects, insert only the contradictory pair $z\vee z\vee z$ and $\mathrm{\neg }z\vee \mathrm{\neg }z\vee \mathrm{\neg }z$ on a fresh bit reserved to $\sigma$; do not insert an empty clause. Otherwise $Q_{\sigma }\mathrm{\ne }\mathrm{\varnothing }$: for every $\rho \in P_{\sigma }$ insert $C_{\sigma ,\rho }={\bigvee }_{i\in Q_{\sigma }}{\mathrm{\ell }}_i(\rho )$, where ${\mathrm{\ell }}_i(\rho )$ is $\mathrm{\neg }{\pi }_i$ if $\rho (i)=1$ and ${\pi }_i$ if $\rho (i)=0$. This clause is falsified exactly by the assignments realizing $\rho$. Every inserted clause has width between $1$ and $\max (q,3)$, and the construction is an explicit finite procedure.

Convert each clause of width $d$ into a block of 3-clauses with fresh auxiliary bits reserved to that block: for $d=3$ keep the clause; for $d=2$ write ${\mathrm{\ell }}_1\vee {\mathrm{\ell }}_2\vee {\mathrm{\ell }}_2$; for $d=1$ write ${\mathrm{\ell }}_1\vee {\mathrm{\ell }}_1\vee {\mathrm{\ell }}_1$; for $d\ge 4$ use fresh bits $y_1,\dots ,y_{d-3}$ and the chain ${\mathrm{\ell }}_1\vee {\mathrm{\ell }}_2\vee y_1$, then $\mathrm{\neg }{y}_k\vee {\mathrm{\ell }}_{k+2}\vee y_{k+1}$ for $1\le k\le d-4$, then $\mathrm{\neg }{y}_{d-3}\vee {\mathrm{\ell }}_{d-1}\vee {\mathrm{\ell }}_d$; each written clause has exactly three literal occurrences, so $F_x$ is a 3-CNF in the format of [F4], and distinct blocks share no auxiliary bit.

For $1\le d\le 3$, padding or keeping a clause preserves its truth value. For $d\ge 4$, if all original literals are false, satisfying the first clause would force $y_1$ true, the intermediate clauses would force all subsequent $y_i$ true, and the last clause would then be false; thus every auxiliary assignment falsifies at least one clause. Conversely, if ${\mathrm{\ell }}_k$ is true, assigning $y_i$ true for $i\le k-2$ and false for $i\ge k-1$ satisfies the whole chain. The tautology of step 2.1 is always satisfied, while its contradictory pair always has exactly one falsified clause.