Degree-anonymization using edge rotations

Cristina Bazgan, Pierre Cazals, Janka Chlebikova

Research output: Contribution to journalArticlepeer-review

Abstract

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

Keywords

  • Degree-anonymization
  • NP-hardness
  • Approximation algorithm

Fingerprint

Dive into the research topics of 'Degree-anonymization using edge rotations'. Together they form a unique fingerprint.

Cite this