The complexity of degree anonymization by vertex addition

•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.