@inproceedings{8df7b6d4b2cd47ee96ee9db7b66d599a,
title = "The complexity of finding a large subgraph under anonymity constraints",
abstract = "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.",
author = "R. Bredereck and S. Hartung and A. Nichterlein and G.J. Woeginger",
year = "2013",
doi = "10.1007/978-3-642-45030-3\_15",
language = "English",
isbn = "978-3-642-45029-7",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "152--162",
editor = "L. Cai and S.-W. Chen and T.-W. Lam",
booktitle = "Algorithms and Computation (24th International Symposium, ISAAC 2013, Hong Kong, December 16-18, 2013. Proceedings)",
address = "Germany",
note = "conference; 24th International Symposium on Algorithms and Computatio; 2013-12-16; 2013-12-18 ; Conference date: 16-12-2013 Through 18-12-2013",
}