@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",

}