TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 14.05.2014


Page Content

to Navigation

Parameterized Inapproximability of Degree Anonymization by Edge Addition and Deletion

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.

14.05.2014 16:15
André Nichterlein
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe