direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

The Complexity of Finding a Large Subgraph Under Anonymity Constraints

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

We define and analyze an anonymization problem in undirected graphs, which is motivated by certain privacy issues in social networks. The goal is to remove a small number of vertices from the graph such that in the resulting subgraph every occurring vertex degree occurs many times.
We prove that the problem is NP-hard for trees, and also for a number of other highly structured graph classes. Furthermore, we provide polynomial time algorithms for other graph classes (like threshold graphs), and thereby establish a sharp borderline between hard and easy cases of the problem. Finally we perform a parametrized analysis, and we concisely characterize combinations of natural parameters that allow FPT algorithms.

12.12.2013 16:15
André Nichterlein
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras