Skip to content

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

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

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 languageEnglish
Title of host publicationCombinatorial Optimization and Applications
Subtitle of host publication14th International Conference, COCOA 2020, Dallas, TX, USA, December 11–13, 2020, Proceedings
EditorsWeili Wu, Zhongnan Zhang
Number of pages12
ISBN (Electronic)978-3-030-64843-5
ISBN (Print)978-3-030-64842-8
Publication statusPublished - 4 Dec 2020
Event14th Annual International Conference on Combinatorial Optimization and Applications - Dallas, United States
Duration: 11 Dec 202013 Dec 2020
Conference number: 14

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference14th Annual International Conference on Combinatorial Optimization and Applications
Abbreviated titleCOCOA
CountryUnited States
Internet address


  • Cocoa2020

    Rights statement: This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at:

    Accepted author manuscript (Post-print), 356 KB, PDF document

    Due to publisher’s copyright restrictions, this document is not freely available to download from this website until: 4/12/21

Related information

Relations Get citation (various referencing formats)

ID: 22856906