cover of size $\leq t$, if and only if there exists a $k$-anonymization solution of cost $\leq ABC+t$. This would prove the required NP-hardness. We next proceed to prove the above claim. We split the proof into two parts.

First, we shall argue that if the given graph has a vertex cover of size $\leq t$, then there exists a $k$-anonymization solution with extra cost $\leq t$. Suppose $C$ is a vertex cover of size $\leq t$. We shall construct a $k$-anonymization solution $\sigma$ in which the critical rows corresponding to the vertices in the cover $C$ pay an extra cost of 1 and every other row pays no extra cost.

For each edge $(x, y)$, if $x\in C$, then [*attach*]{} the edge to $x$, else attach it to $y$. (If both the endpoints of the edge are in the cover, the edge can be attached arbitrarily to any one of the two vertices). Without loss of generality, assume that each vertex in the cover has at least one edge attached to it. Otherwise, the vertex can be safely removed from $C$, yielding a smaller cover.

  -------------------- ----------------
                       
   Case: $u\not\in C$   Case: $u\in C$
  -------------------- ----------------

Form a $k$-anonymization solution 