Abstract (EN)

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