cost of at least 1. Therefore, $$\mbox{total extra cost of $\sigma$} \geq |V'| + |E'|.$$

Construct a vertex cover $C$ as follows. Add every imperfect vertex to $C$. For each edge in $E'$, add one of its endpoints (arbitrarily) to $C$. Clearly, $C$ is a vertex cover. So, $$|C| \leq |V'|+|E'| \leq \mbox{extra cost of $\sigma$}$$

We have proved the following claim:

[Claim 4: ]{} If there exists a $k$-anonymization solution $\sigma$ of extra cost $\leq t$, then there exists a vertex cover of size $\leq t$. [$\Box$]{}

We observed that the cost of a $k$-anonymous solution is the sum of $ABC$ and the extra cost of the solution. Now, by combining Claim 1 and Claim 4, we get the following: there exists a vertex cover of size $\leq t$, if and only if there exists a $k$-anonymization solution of cost $\leq ABC+t$. This completes the NP-hardness proof. [$\Box$]{}

It is easy to show that our reduction is an $L$-reduction (see [@Papa] for a discussion on $L$-reductions). As the vertex cover problem on 3-regular graphs is MAXSNP-hard [@Alimonti], it follows that,

\[thm:BBB\] The $k$-anonymization problem is MAXSNP-hard, even when the number of columns in 3 and the privacy parameter is 