TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 03.07.2013

isti-logo

Page Content

to Navigation

A Refined Complexity Analysis of Degree Anonymization in Graphs

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

Motivated by a strongly growing interest in graph anonymization in the data mining and databases communities, we study the NP-hard problem of making a graph k-anonymous by adding as few edges as possible. Herein, a graph is k-anonymous if for every vertex in the graph there are at least k >= 1 other vertices of the same degree. Our algorithmic results shed light on the performance quality of a popular heuristic due to Liu and Terzi [ACM SIGMOD 2008]; in particular, we show that the heuristic provides optimal solutions in case that many edges need to be added. Based on this, we develop a polynomial-time data reduction, yielding a polynomial-size problem kernel for the problem parameterized by the maximum vertex degree. This result is in a sense tight since we also show that the problem is already NP-hard for H-index three, implying NP-hardness for smaller parameters such as average degree and degeneracy.

Date
Speaker
Location
Language
03.07.2013 16:15
André Nichterlein
TEL 512
english/german

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe