Skip to content

Degree-anonymization using edge rotations

Research output: Contribution to journalArticlepeer-review

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 −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, ≥ 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 = n and for trees when = θ(n). Additionally, we establish sufficient conditions for an input graph and k such that a solution for Min Anonymous-Edge-Rotation exists.
Original languageEnglish
Pages (from-to)1-15
Number of pages15
JournalTheoretical Computer Science
Volume873
Early online date28 Apr 2021
DOIs
Publication statusPublished - 10 Jun 2021

Documents

  • Degree_anonymization_using_edge_rotations

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

    Due to publisher’s copyright restrictions, this document is not freely available to download from this website until: 28/04/22

    Licence: CC BY-NC-ND

Related information

Relations Get citation (various referencing formats)

ID: 27293260