Item

Abstract

The NP-hard \textsck-Anonymity} problem asks, given an~n × m-matrix~M over a fixed alphabet and an integer~s>0, whether~M can be made k-anonymous by suppressing (blanking out) at most~s entries. A matrix~M is said to be k-anonymous if for each row~r in~M there are at least~k-1 other rows in~M which are identical to~r. Complementing previous work, we introduce two new ``data-driven'' parameterizations for \textsc{k-Anonymity}---the number~\tin of different input rows and the number~→ut of different output rows---both modeling aspects of data homogeneity. We show that \textsc{k-Anonymity} is fixed-parameter tractable for the parameter~\tin, and it is NP-hard even for~→ut = 2 and alphabet size four. Notably, our fixed-parameter tractability result implies that \textsc{k-Anonymity} can be solved in \emph{linear time} when~\tin is a constant. Our results also extend to some interesting generalizations of \textsc{k-Anonymity.