TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 12.12.2013

isti-logo

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.

Date
Speaker
Location
Language
12.12.2013 16:15
André Nichterlein
TEL 512
english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe