A refined complexity analysis of degree anonymization in graphs
作者： Sepp Hartung , André Nichterlein , Rolf Niedermeier , Ondřej Suchý , None
关键词:
摘要: Motivated by a strongly growing interest in graph anonymization, we study the NP-hard Degree Anonymity problem asking whether can be made k-anonymous adding at most given number of edges. Herein, is if for every vertex there are least k - 1 other vertices same degree. Our algorithmic results shed light on performance quality popular heuristic due to Liu and Terzi ACM SIGMOD 2008]; particular, show that provides optimal solutions "many" edges need added. Based this, develop polynomial-time data reduction yielding polynomial-size kernel parameterized maximum In terms complexity analysis, this result sense tight since also already H-index three, implying NP-hardness smaller parameters such as average degree degeneracy.
springer.com
acm.org
elsevier.com
sci-hub.se 参考文章(49)
Xuesong Lu, Yi Song, Stéphane Bressan, Fast Identity Anonymization on Graphs Lecture Notes in Computer Science. pp. 281- 295 ,(2012) , 10.1007/978-3-642-32600-4_21
Robert Bredereck, Sepp Hartung, André Nichterlein, Gerhard J. Woeginger, The Complexity of Finding a Large Subgraph under Anonymity Constraints Algorithms and Computation. pp. 152- 162 ,(2013) , 10.1007/978-3-642-45030-3_15
J. Flum, M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series) ,(2006)
Christian Komusiewicz, Rolf Niedermeier, New races in parameterized algorithmics mathematical foundations of computer science. pp. 19- 30 ,(2012) , 10.1007/978-3-642-32589-2_2
Robert Bredereck, Vincent Froese, Sepp Hartung, André Nichterlein, Rolf Niedermeier, Nimrod Talmon, The Complexity of Degree Anonymization by Vertex Addition Algorithmic Aspects in Information and Management. pp. 44- 55 ,(2014) , 10.1007/978-3-319-07956-1_5
Cristina Bazgan, André Nichterlein, Parameterized Inapproximability of Degree Anonymization Parameterized and Exact Computation. pp. 75- 84 ,(2014) , 10.1007/978-3-319-13524-3_7
Alex Thomo, Bruce M. Kapron, S. Venkatesh, Gautam Srivastava, Sean Chester, Ganesh Ramesh, k-Anonymization of Social Networks by Vertex Addition. advances in databases and information systems. pp. 107- 116 ,(2011)
Rolf Niedermeier, Reflections on Multivariate Algorithmics and Problem Parameterization symposium on theoretical aspects of computer science. ,vol. 5, pp. 17- 32 ,(2010) , 10.4230/LIPICS.STACS.2010.2495
Rolf Niedermeier, Invitation to fixed-parameter algorithms ,(2006)
Jörg Flum, Martin Grohe, Parameterized complexity theory Springer. ,(2010)