Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse




Conference Paper

The Effect of Homogeneity on the Complexity of k-Anonymity

There are no MPG-Authors available
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Bredereck, R., Nichterlein, A., Niedermeier, R., & Philip, G. (2011). The Effect of Homogeneity on the Complexity of k-Anonymity. In O. Owe, M. Steffen, & J. A. Telle (Eds.), Fundamentals of Computation Theory (pp. 53-64). Berlin: Springer. doi:10.1007/978-3-642-22953-4_5.

Cite as:
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.