# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### The Effect of Homogeneity on the Complexity of k-Anonymity

##### MPS-Authors

There are no MPG-Authors available

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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 (*Fundamentals of Computation Theory* (pp. 53-64). Berlin: Springer. doi:10.1007/978-3-642-22953-4_5.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0019-DC22-6

##### 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.