کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435716 | 689930 | 2015 | 19 صفحه PDF | دانلود رایگان |
• Degree anonymization by vertex addition is computationally intractable in general.
• Posing structural restrictions on the edges connected to the new vertices seems to make the problem even harder.
• There are some tractable special cases, for example, when the number of new edges is small.
Motivated by applications in privacy-preserving data publishing, we study the problem of making an undirected graph k-anonymous by adding few vertices (together with some incident edges). That is, after adding these “dummy vertices”, for every vertex degree d appearing in the resulting graph, there shall be at least k vertices with degree d. We explore three variants of vertex addition (justified by real-world considerations) and study their (parameterized) computational complexity. We derive mostly intractability results, even for very restricted cases (including trees and bounded-degree graphs) but also obtain some encouraging fixed-parameter tractability results.
Journal: Theoretical Computer Science - Volume 607, Part 1, 23 November 2015, Pages 16–34