Degree-anonymization using edge rotations

The Min Anonymous-Edge-Rotation problem asks for an input graph G and a positive integer k to find aminimum number of edge rotations that transform G into a graph such that for each vertex there are at least k −1 other vertices of the same degree (a k-degree-anonymous graph). In this paper, we prove that the Min Anonymous-Edge-Rotation problem is NP-hard even for k = n/q, where n is the order of a graph and q any positive integer, q ≥ 3. We argue that under some constrains on the number of edges in a graph and k, Min Anonymous-Edge-Rotation is polynomial-time 2-approximable. Furthermore, we show that the problem is solvable in polynomial time for any graph when k = n and for trees when k = θ(n). Additionally, we establish sufficient conditions for an input graph and k such that a solution for Min Anonymous-Edge-Rotation exists.