Dipl.-Inf. André Nichterlein (TU Berlin)

We analyze an anonymization problem in undirected graphs which is motivated by certain privacy issues in social networks. The goal is to add or to delete a small number of vertices from the graph such that in the resulting subgraph every occurring vertex degree occurs many times.
We show strong inapproximability results when only edge deletions or only edge additions are allowed, even if we allow running times of the form f(s) poly(n) where f is an arbitrary function depending only on the number s of edge deletions (additions). However, these results do not hold if edge additions and deletions are allowed.
On the positive side, the problem is fixed-parameter tractable with respect to the combined parameter number of allowed edge editions and maximum vertex degree.
This is work in progress.

Back to the research colloquium site.