?, u, ?\rangle$ pay a cost of $2$ each, totaling $14$; (iv) The three (type \[type:DDD\]) rows of the form $\langle 0, u, Z\rangle$ pay cost of $3$ in total; (v) The three (type \[type:EEE\]) rows of the form $\langle 0, Z, u \rangle$ pay cost of $3$ in total. Thus, the total base cost for each vertex $u$ is $27$. Then, each edge has a base cost of 2, coming from the two rows corresponding to it. The two blocks dummy rows (of type \[type:DDD-A\] and type \[type:DDD-B\]) contribute a base cost of $7$ each, summing up to $14$. Thus, the [*aggregated base cost*]{} is $ABC = 27r + 2|E|+14$. For any row, the difference between the actual cost paid and the base cost is denoted as [*extra cost*]{}. Similarly, the total extra cost is the sum of extra costs over all the rows. Notice that the cost of the solution is the sum of $ABC$ and the total extra cost.

We claim that the given graph has a vertex cover of size $\leq t$, if and only if there exists a $k$-anonymization solution with an extra cost $\leq t$. It would follow that the graph has a vertex 