TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 12.12.2013


Page Content

to Navigation

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.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe