|S_i|\cdot a(S_i)$.

We shall interchangeably use either of the two descriptions in our discussions.

Hardness Results with Three Columns
===================================

In this section, we present results on the complexity of $k$-anonymization problem when both the number of columns and the privacy parameter are constants.

NP-Hardness
-----------

\[thm:AAA\] The $k$-anonymization problem is NP-hard even when the number of columns $m$ is 3 and the privacy parameter is fixed as $k=7$.

[[*Proof:* ]{}]{}We give a reduction from the vertex cover problem on 3-regular graphs, which is known to be NP-hard (see [@GJ]). Recall that a vertex cover of a graph refers to a subset of vertices such that each edge has at least one endpoint in the subset and that a graph is said to be 3-regular, if every vertex has degree exactly 3.

Let $G=(V,E)$ be the input 3-regular graph having $r$ vertices. The alphabet of the output table is as follows: For each vertex $u \in V$, we add a symbol $u$. Next, we have additional symbols ‘$0$’ and ‘$Z$’. Further, we need a number of [*special*]{} symbols. A special symbol appears only once in the whole of the table. The exposition becomes somewhat clumsy, if we explicitly introduce these 