and new results put together provide a complete picture on the complexity of the problem for the four cases of the number of columns $m$ and the alphabet size $\Sigma$ being fixed constants or arbitrarily large. This is shown in Figure \[fig:summary\].

  -- ------------------------------------------------------------------------------------------------------------------------------------------------- --
                                                                                                                                                       

         $\mathbf{|\Sigma|}$**[=constant]{} &     $\mathbf{|\Sigma|}$**[=arbitrary]{}\                                                                 
     & &\                                                                                                                                              
     & &\                                                                                                                                              
     $\mathbf{m}$**[=constant]{} & Solvable in P (even when $k$ is arbitrary) \[This paper\] & NP-hard (even when $k$ is a constant) \[This paper\]\   
     & &\                                                                                                                                              
     & &\                                                                                                                                              
     $\mathbf{m}$**[=arbitrary]{} & NP-hard (even when $k$ is a constant) [@ICDT] & NP-hard (even when $k$ is a constant) [@ICDT]\                     
     & &\                                                                                                                                              
     ********                                                                                                                                          
  -- ------------------------------------------------------------------------------------------------------------------------------------------------- --

Problem Definition
==================

The input to the $k$-anonymization problem is a $n\times m$ table $T$ having $n$ rows and $m$ columns, with symbols of the table drawn from an alphabet $\Sigma$. The input also includes a [*privacy parameter*]{} $k$. A feasible solution $\sigma$ transforms the given table $T$ to a new table $T'$ by suppressing some of the cells of $T$; namely, it replaces some of the cells of $T$ with “$*$”. In the transformed table $T'$, for any row $t$, there should exist $k-1$ other rows that are identical to $t$. The cost of the solution, 