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.
|Name||Lecture Notes in Computer Science|
|Conference||conference; 24th International Symposium on Algorithms and Computatio; 2013-12-16; 2013-12-18|
|Period||16/12/13 → 18/12/13|
|Other||24th International Symposium on Algorithms and Computatio|