. . . "A Refined Complexity Analysis of Identity Anonymization on Graphs"@en . . "4"^^ . . "0302-9743" . "Springer Science+Business Media" . "A Refined Complexity Analysis of Identity Anonymization on Graphs" . "10.1007/978-3-642-39212-2_52" . . . "A Refined Complexity Analysis of Identity Anonymization on Graphs"@en . . "1"^^ . "978-3-642-39211-5" . . "A Refined Complexity Analysis of Identity Anonymization on Graphs" . "Riga" . "I" . "RIV/68407700:21240/13:00209346" . "Hartung, S." . . "Berlin" . "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)" . "Parameterized Complexity; Identity Anonymization; Kernelization; Bounded degree; NP-hardness"@en . "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." . . . "RIV/68407700:21240/13:00209346!RIV14-MSM-21240___" . "Niedermeier, R." . . "http://link.springer.com/chapter/10.1007%2F978-3-642-39212-2_52" . . . "13"^^ . "[F8AE480E9F81]" . "58999" . "2013-07-08+02:00"^^ . "21240" . "Nichterlein, A." . "Such\u00FD, Ond\u0159ej" . "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."@en . . . .