# How to get a degree-anonymous graph using minimum number of edge rotations

Cristina Bazgan, Pierre Cazals, Janka Chlebikova

Research output: Chapter in Book/Report/Conference proceedingConference contribution

## Abstract

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. The Min Anonymous-Edge-Rotation problem 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).
Original language English Combinatorial Optimization and Applications 14th International Conference, COCOA 2020, Dallas, TX, USA, December 11–13, 2020, Proceedings Weili Wu, Zhongnan Zhang Springer 242-256 12 978-3-030-64843-5 978-3-030-64842-8 https://doi.org/10.1007/978-3-030-64843-5_17 Published - 4 Dec 2020 14th Annual International Conference on Combinatorial Optimization and Applications - Dallas, United StatesDuration: 11 Dec 2020 → 13 Dec 2020Conference number: 14https://theory.utdallas.edu/COCOA2020/index.html

### Publication series

Name Lecture Notes in Computer Science Springer 12577 0302-9743 1611-3349

### Conference

Conference 14th Annual International Conference on Combinatorial Optimization and Applications COCOA United States Dallas 11/12/20 → 13/12/20 https://theory.utdallas.edu/COCOA2020/index.html

## Keywords

• degree-anonymous graph
• edge rotations
• NPhardness
• approximation algorithm

## Fingerprint

Dive into the research topics of 'How to get a degree-anonymous graph using minimum number of edge rotations'. Together they form a unique fingerprint.