Inhalt des Dokuments
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
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.