u\rangle$ to this cluster. Notice that the seven rows each pay a cost of $2$, and hence their extra cost is $0$. [*The critical row pays a cost of $2$, and hence, its extra cost is $1$*]{}.

Observe that all the rows of the table have been assigned to some cluster and each cluster has size at least $7$. From the above discussion, we see that the only rows having non-zero extra cost are the critical rows corresponding to the vertices in the cover $C$ and they pay an extra cost of $1$ each. We conclude that the total extra cost is $|C|$. We have proved the following claim:

[Claim 1: ]{} If the given graph has a vertex cover of size $\leq t$, then there exists a $k$-anonymization solution with extra cost $\leq t$.

We next proceed to prove the reverse direction: if there exists a $k$-anonymization solution $\sigma$ of extra cost $\leq t$, then there exists a vertex cover of size $\leq t$. Consider such a solution $\sigma$. We first make the following claim.

[Claim 2: ]{} Consider a vertex $u$. Suppose the critical row $\langle ?, u, u\rangle$ pays an extra cost of 0. Then, the only 