takes an instance $I_1$ of the problem $P_1$ as input and outputs an instance $I_2$ of the problem $P_2$. The algorithm $S$ takes as input a solution $S_2$ of the instance $I_2$ and produces a solution $S_1$ for the instance $I_1$. The following two requirements are to be met, for some constants $\alpha$ and $\beta$: (i) ${{\rm OPT}}(I_2)\leq \alpha {{\rm OPT}}(I_1)$; (ii) ${{\rm Cost}}(S_1) - {{\rm OPT}}(I_1) \leq \beta ({{\rm Cost}}(S_2) - {{\rm OPT}}(I_2))$.

Let $G=(V,E)$ be the input 3-regular graph over $r$ vertices. The reduction given in Theorem \[thm:AAA\] produces a table $T$; this constitutes the required algorithm $R$. Let $C^*$ be the optimal vertex cover of $G$. In Theorem \[thm:AAA\], we showed (in Claim 1) that given a cover of size at most $t$, we can construct a $k$-anonymization solution $\sigma$ of cost at most $ABC+t$. It follows that the optimal $k$-anonymization solution satisfies ${{\rm Cost}}(\sigma^*)\leq ABC+|C^*|$. Recall that $ABC = 27r+2|E|+14$. Since the graph is 3-regular, number of edges is $|E|=3r/2$. Thus, $ABC=30r+14$. For sufficiently large $r$, we have $ABC\leq 31r$. Since $G$ is 3-regular, a vertex can cover at most three edges and so, $|C^*|\geq r/2$. It follows that $ABC \leq 62r$ and that ${{\rm Cost}}(\sigma^*)\leq 