Fixed-parameter tractability of anonymizing data by suppressing entries

A popular model for protecting privacy when person-specific data is released is k -anonymity. A dataset is k-anonymous if each record is identical to at least (k-1) other records in the dataset. The basic k-anonymization problem, which minimizes the number of dataset entries that must be suppressed to achieve k-anonymity, is NP-hard and hence not solvable both quickly and optimally in general. We apply parameterized complexity analysis to explore algorithmic options for restricted versions of this problem that occur in practice. We present the first fixed-parameter algorithms for this problem and identify key techniques that can be applied to this and other k-anonymization problems.