On the complexity of restricted k-anonymity problem

Abstract. One of the emerging concepts in microdata protection is k-anonymity, introduced by Samarati and Sweeney. k-anonymity provides a simple and efficient approach to protect private individual information and is gaining increasing popularity. k-anonymity requires that every tu-ple(record) in the microdata table released be indistinguishably related to no fewer than k respondents. In this paper, we introduce two new vari-ants of the k-anonymity problem, namely, the Restricted k-anonymity problem and Restricted k-anonymity problem on attribute (where sup-pressing the entire attribute is allowed). We prove that both problems are NP-hard for k ≥ 3. The results imply the main results obtained by Meyerson and Williams. On the positive side, we develop a polyno-mial time algorithm for the Restricted 2-anonymity problem by giving a graphical representation of the microdata table.