Cristina Bazgan
email: cristina.bazgan@dauphine.fr

Pierre Cazals
email: pierre.cazals@dauphine.eu

Janka Chlebíková
email: janka.chlebikova@port.ac.uk

Degree-anonymization using edge rotations

Keywords: Degree-anonymization, NP-hardness, Approximation algorithm

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In recent years huge amounts of personal data has been collected on various networks as e.g. Facebook, Instagram, Twitter or LinkedIn. Ensuring the privacy of network users is one of the main research tasks. One possible model to formalise these issues was introduced by Liu and Terzi [START_REF] Liu | Towards identity anonymization on graphs[END_REF] who transferred the k-degree-anonymity concept from tabular data in databases [START_REF] Fung | Privacy-preserving data publishing: A survey of recent developments[END_REF] to graphs which are often used as a representation of networks. Following this study a graph is called k-degree-anonymous if for its each vertex there are at least k -1 other vertices with the same degree. The parameter k represents the number of vertices that are mixed together and thus the increasing value of k increases the level of anonymity. In [START_REF] Wu | A survey of privacypreservation of graphs and social networks[END_REF], Wu et al. presented a survey of different anonymization models and some of their weaknesses. Casas Roma et al. [START_REF] Casas-Roma | A survey of graph-modification techniques for privacy-preserving on networks[END_REF] proposed a survey of several graph-modification techniques for privacy-preserving on networks. In this paper we consider the k-degree-anonymous concept of Liu and Terzi [START_REF] Liu | Towards identity anonymization on graphs[END_REF].

The main study problem related to k-degree anonymous graphs is to find a minimum number of graph operations to transform an input graph to a k-degree anonymous graph.

Different graph operations of transforming a graph into a k-degree-anonymous one are considered in research papers where the operations maybe the following: delete vertex/edge, add vertex/edge, or add/delete edge (see more details later). One advantage in the approaches based on vertex/edge deletion/adding is that a solution always exists since in the worst case scenario one can consider the empty or the complete graph that is k-degree-anonymous for any k (at most the number of vertices of the graph). However, the basic graph parameters as the number of vertices and edges could be modified with such transformations.

Vertex/edge modification versions associated to k-degree-anonymity have been relatively well studied. Hartung et al. [START_REF] Hartung | Improved upper and lower bound heuristics for degree anonymization in social networks[END_REF][START_REF] Hartung | A refined complexity analysis of degree anonymization in graphs[END_REF] studied the edge adding modification as proposed by Liu and Terzi [START_REF] Liu | Towards identity anonymization on graphs[END_REF]. For this type of modification Chester et al. [START_REF] Chester | Complexity of social network anonymization[END_REF] established a polynomial time algorithm for bipartite graphs.

The variant of adding vertices instead of edges was studied by Chester et al. in [START_REF] Chester | Why waldo befriended the dummy? k-anonymization of social networks with pseudo-nodes[END_REF] where they presented an approximation algorithm with an additive error. Bredereck et al. [START_REF] Bredereck | The complexity of degree anonymization by vertex addition[END_REF] investigated the parameterized complexity of several variants of vertex adding which differ in the way the inserted vertices can be adjacent to existing vertices. Concerning the vertex deletion variant, Bazgan et al. [START_REF] Bazgan | Finding large degree-anonymous subgraphs is hard[END_REF] showed the NP-hardness even on very restricted graph classes such as trees, split graphs, or trivially perfect graphs. Moreover, in [START_REF] Bazgan | Finding large degree-anonymous subgraphs is hard[END_REF] the vertex and edge deletion variants are proved intractable from the approximability and parameterized complexity point of view.

Several papers study the basic properties of edge rotations, including some bounds for the minimum number of edge rotations between two graphs [START_REF] Chartrand | Rotation and jump distances between graphs[END_REF][START_REF] Chartrand | Edge rotations and distance between graphs[END_REF][START_REF] Ralph J Faudree | On the rotation distance of graphs[END_REF][START_REF] Goddard | Distances between graphs under edge operations[END_REF][START_REF] Elzbieta | Edge rotation and edge slide distance graphs[END_REF].

In this paper we consider the version of transforming a graph into a kdegree-anonymous one using edge rotations which don't modify the number of vertices/edges. It should be noticed that in such case a solution may not always exist, as we discuss in Section 3.

To the best of our knowledge the problem of transforming a graph to a kdegree anonymous graph using the edge rotations has not been fully explored. In some particular cases some research has been done in [START_REF] Salas | Graphic sequences, distances and k-degree anonymity[END_REF] where the authors study the edge rotation distance and various metric between the degree sequences to find a "closest" regular graph. In paper [START_REF] Casas-Roma | An algorithm for k-degree anonymity on large networks[END_REF] the authors proposed an heuristic to compute the edge rotation distance to a k-degree anonymous graph.

Our results. In this paper we study the various aspects of the Min Anonymous-Edge-Rotation problem. An input to the problem is an undirected graph G = (V, E) with n vertices and m edges and an integer k ≤ n. The goal is to find a shortest sequence of edge rotations that transforms G into a k-degree-anonymous graph, if such a sequence exists. We first show that when n 2 ≤ m ≤ n(n-3) 2 and k ≤ n 4 a solution always exists. Moreover for trees a solution exists if and only if 2m

n is an integer. We prove that Min Anonymous-Edge-Rotation is NP-hard even when k = n q and q ≥ 3 is a fixed positive integer. On the positive side we provide a polynomial-time 2-approximable algorithm under some constraints. Finally, we demonstrate that Min Anonymous-Edge-Rotation is solvable in polynomial time for trees when k = θ(n) and for any graph when k = n.

Our paper is organized as follows. Some preliminaries about edge rotations and our formal definitions are given in Section 2. The study of feasibility is initiated in Section 3. Section 4 presents the NP-hardness proof. In Section 5 we study properties of the specific k-degree anonymous degree sequences that are used in Section 6 to present a polynomial-time 2-approximation algorithm and in Section 7 to establish a polynomial time algorithm for trees. Moreover in Section 7 we consider the case k = n in general graphs. Some conclusions are given at the end of the paper.

Preliminaries

In this paper we assume that all graphs are undirected, without loops and multiple edges, and not necessary connected graphs.

Let G = (V, E) be a graph. For a vertex v ∈ V , let deg G (v) be the degree of v in G, and ∆ G be the maximum degree of G.

A vertex v with degree deg G (v) = |V | -1 is called a universal vertex. The neighborhood of v in G is denoted by N G (v) = {u ∈ V : uv ∈ E} and Inc G (v) is the set of all edges incident to v, Inc G (v) = {e ∈ E : v ∈ e}.
If the underlying graph G is clear from the context, we omit the subscript G.

Definition 1. Given a graph G = (V, E) of order n, the degree sequence S G of G is the non-increasing sequence of its vertex degrees,

S G = (deg(v 1 ), . . . , deg(v n )), where deg(v 1 ) ≥ deg(v 2 ) ≥ • • • ≥ deg(v n ). Definition 2. A sequence D of non-negative integers D = (d 1 , d 2 , . . . , d n ) is graphic if
there exists a graph G such that its degree sequence coincides with D.

As follows from Erdős-Gallai theorem (see e.g. [START_REF] Erdős | Gráfok eloírt fokú pontokkal (graphs with points of prescribed degrees, in Hungarian)[END_REF]) the necessary and sufficient conditions for a non-increasing sequence D = (d 1 , d 2 , . . . , d n ) to be graphic are:

n i=1 d i is even (1) i=1 d i ≤ ( -1) + n i= +1 min(d i , ) holds for any 1 ≤ ≤ n. (2)
Furthermore, it is an easy exercise to prove that a sequence of integers D = (d 1 , d 2 , . . . , d n ) corresponds to a degree sequence of a tree on n vertices if and only if each d i ≥ 1 and

n i=1 d i = 2(n -1).
Let G(n, m) be the set of all graphs with n vertices and m edges.

Definition 3. Let G, G ∈ G(n, m).
We say that G can be obtained from G by an edge rotation (uv, uw) if V (G) = V (G ) and there exist three distinct vertices u, v and w in G such that uv ∈ E(G), uw / ∈ E(G), and E(G ) = (E(G) \ {uv}) ∪ {uw}, see Figure 1.

u v w

G such that deg G (v) = deg G (v) -1, deg G (w) = deg G (w)+1
, and the degree of the other vertices is not changed. Let define a (+1, -1)-degree modification of the degree sequence D = (d Note that a solution to the Min Anonymous-Edge-Rotation problem may not exist for all instances. For example, if G is a complete graph without an edge, K n \ {e}, n ≥ 6, then there is no solution for such graph G and k = 3. Therefore, we are only interested in studying of feasible instances (G, k) defined as an instance for which there exists a solution to Min Anonymous-Edge-Rotation. Our initial study of sufficient conditions for feasibility is presented in Section 3.

Obviously, since all graphs are 1-degree-anonymous, we are only interested in cases where k ≥ 2.

The decision version associated to Min Anonymous-Edge-Rotation is defined as follows for a feasible instance (G, k):

Anonymous-Edge-Rotation Input: (G, k, r) where G = (V, E) is an undirected graph, k ∈ {1, . . . , |V |}, and r be a positive integer. Question: Is there a sequence of + 1 graphs G 0 = G, G 1 , G 2 , . . . , G such that ≤ r, G i+1 can be obtained from G i by one edge rotation, and G is k-degree-anonymous?

We also consider the Min Anonymous-Edge-Rotation problem in restricted graph classes, e.g. trees. In that case we require that all graphs in the sequence G 0 , . . . , G must be from the same graph class. Note that the problem can also be studied without this requirement, but the results may be different.

The following theorem shows important properties about the edge rotations. The result was already proved in [START_REF] Chartrand | Edge rotations and distance between graphs[END_REF], but due to the simplicity of our approach, we present an another proof here.

Theorem 1. For any two graphs G, G ∈ G(n, m), we can transform G to G using a sequence of edge rotations.

Proof. Let E 1 = E(G) \ (E(G) ∩ E(G )) be the set of edges that are in G and not in G and E 2 = E(G ) \ (E(G) ∩ E(G )) be the set of edges that are in G and not in G. For all u, v and w such as uv ∈ E 1 and uw ∈ E 2 , we add one edge rotation (uv, uw). In all other cases, let uv ∈ E 1 and u v ∈ E 2 , where all vertices u, v, u , v are distinct. There are two case: 1) uu , uv , vu and vv ∈ E(G) or 2) at least one of these four edges is missing.

In the first case we can make the following two edge rotations to move uv from G to u v in G : (v v, v u ) and (vu, vv ) (see Figure 2). In the second case, if for example vv is missing, we can use the following two rotations (vu, vv ) and then (v v, v u ) (see Figure 3) and similarly if another edge is missing.

Feasibility study

As it was discussed in Section 2, the Min Anonymous-Edge-Rotation problem does not have a solution for every input instance. It is not difficult to see that if a graph is 'almost' complete or 'almost' empty, then there are only restricted options on the number of different degree classes and therefore a solution may not exist.

First we present some sufficient conditions for an instance to be feasible showing that if a graph is not 'almost' complete or an empty graph, then a solution of the problem exists for all k ≤ n 4 , where n is the order of the graph.

Theorem 2. Let G ∈ G(n, m) such that n 2 ≤ m ≤ n(n-3)
= 2m n . Type 1: k ≤ s ≤ n -k Let D 1 = (d 1 1 , d 1 2 , . . . , d 1 s , d 2 1 , d 2 2 , . . . , d 2 n-s
) be a sequence of positive integers where for all i,

1 ≤ i ≤ s, d 1 i = d + 1 and for all j, 1 ≤ j ≤ n -s, d 2 j = d
(see Figure 4). The sequence contains n elements and it is easy to see that

s i=1 (d + 1) + n-s j=1 d = 2m. s n -s d + 1 d Figure 4: The sequence D 1 Following the assumptions s ≥ k and n -s ≥ k, therefore D 1 is a k-anonymous sequence. Type 2 : s < k Let D 2 = (d 1 1 , d 1 2 , . . . , d 1 s+k , d 2 1 , d 2 2 , . . . , d 2 n-s-2k , d 3 1 , d 3 2 , . . . , d 3
k ) be a sequence of positive integers where for all i, 5). The sequence contains n elements and

1 ≤ i ≤ s + k, d 1 i = d + 1; for all r, 1 ≤ r ≤ n -s -2k, d 2 r = d; for all j, 1 ≤ j ≤ k, d 3 j = d -1 (see Figure
s+k i=1 (d + 1) + k j=1 (d -1) + n-s-2k =1 d = 2m s + k n -s -2k k d + 1 d d -1 Figure 5: The sequence D 2 Since n ≥ 4k and s < k, n -s -2k ≥ k, D 2 is a k-anonymous sequence. Type 3: s > n -k Let D 3 = (d 1 1 , d 1 2 , . . . , d 1 k , d 2 1 , d 2 2 , . . . , d 2 s-2k , d 3 1 , d 3 2 , . . . , d 3 k+n-s
) be a sequence of positive integers where for all i, 6). The sequence has n elements and Now we show that all three sequences are graphic, therefore that the condition ( 2) is true for any . We split the proof into several subcases depending on the value of and the type of the sequence.

1 ≤ i ≤ k, d 1 i = d + 2; for all r, 1 ≤ r ≤ s -2k, d 2 r = d + 1; for all j, 1 ≤ j ≤ k + n -s, d 3 j = d (see Figure
k i=1 (d + 2) + k+n-s j=1 d + s-2k =1 (d + 1) = 2m. k s -2k k + n -s d + 2 d + 1 d
From our assumptions

n 2 ≤ m ≤ n(n-3) 2 , it follows 1 ≤ d ≤ n -3. Case A. = 1 Because d ≥ 1, (2) trivially holds. Case B. = 2, due to n ≥ 8, n j= +1 min(d j , ) ≥ 6d -2 i=1 d i ≤ (d + 2) = 2(d + 2) ≤ 2 + (6d -2) ≤ ( -1) + n j= +1 min(d j , ) Case C. 3 ≤ < d i=1 d i ≤ (d + 2) ≤ (n -1) = n -= 2 -+ n -2 = ( -1) + (n -) ≤ ( -1) + n j= +1 min(d j , ) Case D. 3 ≤ = d, Type 1 & 3: i=1 d i ≤ (d + 2) ≤ (n -1) = n -= 2 -+ n -2 = ( -1) + (n -) ≤ ( -1) + n j= +1 min(d j , )
Type 2, following our assumptions also = d ≤ n -3

i=1 d i ≤ (d+1) = ( +1) = ( -1)+2 ≤ ( -1)+3 -3 = ( -1)+3( -1) = ( -1) + ( + 3 -)( -1) ≤ ( -1) + (n -)( -1) ≤ ( -1) + n j= +1 min(d j , ) Case E. 3 ≤ = d + 1. Furthermore, = d + 1 ≤ n -2. Type 1 & 2, ≥ 4: i=1 d i ≤ (d + 1) = 2 = ( -1) + ≤ ( -1) + 2 -4 = ( -1) + 2( -2) = ( -1) + ( + 2 -)( -2) ≤ ( -1) + (n -)( -2) = ( -1) + (n -)(d -1) ≤ ( -1) + n j= +1 min(d j , ) Type 1 & 2, = 3: Due to n ≥ 8, n j= +1 min(d j , ) ≥ 5d -4 ≥ Therefore i=1 d i ≤ (d + 1) = 2 = ( -1) + ≤ ( -1) + n j= +1 min(d j , ) Type 3, 3 ≤ ≤ n -3 i=1 d i ≤ (d+2) = ( +1) = ( -1)+2 ≤ ( -1)+3 -3 = ( -1)+3( -1) = ( -1) + ( + 3 -)( -1) ≤ ( -1) + (n -)( -1) ≤ ( -1) + n j= +1 min(d j , ) Type 3, = n -2 i=1 d i = k(d+2)+(s-2k)(d+1)+(k+n-s-2)d = nd-2d+s ≤ d(n-2)+n-1 ≤ (n -3)(n -2) + n -1 ≤ ( -1) + 2d = ( -1) + n j= +1 min(d j , ). Case F. 3 ≤ = d + 2. Furthermore, = d + 2 ≤ n -1. Type 1 & 2: i=1 d i ≤ (d + 1) ≤ ( -1) ≤ ( -1) + n j= +1 min(d j , ) Type 3, = 3: Due to n ≥ 8, n j= +1 min(d j , ) ≥ 5 ≥ . Then i=1 d i ≤ (d + 2) = 2 = ( -1) + ≤ ( -1) + n j= +1 min(d j , ) Type 3, 4 ≤ ≤ n -2: i=1 d i ≤ (d + 2) = 2 = ( -1) + ≤ ( -1) + 2 -4 = ( -1) + 2( -2) = ( -1) + ( + 2 -)( -2) ≤ ( -1) + (n -)( -2) ≤ ( -1) + n j= +1 min(d j , )
Type 3, = n -1:

i=1 d i = k(d + 2) + (s -2k)(d + 1) + (k + n -s -1)d = s + nd -d ≤ n -1 + (n -1)(n -3) = (n -1)(n -2) = ( -1) ≤ ( -1) + n j= +1 min(d j , ). Case G. d + 2 < < n i=1 d i ≤ (d + 2) ≤ ( -1) ≤ ( -1) + n j= +1 min(d j , ) Case H. = n i=1 d i ≤ (d + 2) ≤ ( -1)
Therefore, we have proved that there exists a k-degree-anonymous graph G ∈ G(n, m) and the graph G can be transformed to G using a sequence of edge rotations due to Theorem 1. Now we extend the feasibility study to the case k = n for which we get necessary and sufficient conditions. Proof. Since k = n in Min Anonymous-Edge-Rotation, every vertex has to be in the same degree class, so if there is a solution, the resulting graph has to be regular. Moreover, a necessary and sufficient condition for a p-regular graph with n vertices to exist is that n ≥ p + 1 and np must be even [START_REF] Tomescu | Problems in combinatorics and graph theory[END_REF].

If 2m n is not an integer then obviously there is no regular graph in G(n, m) and therefore (G, n) is not a feasible instance.

If 2m n is an integer, since n × 2m n = 2m is even, n ≥ 2m n + 1 there is a 2m nregular graph in G(n, m) as it was mentioned before. By Theorem 1 we conclude that there exists a sequence of edge rotations that leads to a 2m n -regular graph starting from G.

Hardness of Min Anonymous-Edge-Rotation

In this section we show that the decision version of Min Anonymous-Edge-Rotation, the problem Anonymous-Edge-Rotation, is NP-hard. The proof is based on a reduction from the restricted version of a cover set problem, Exact Cover By 3-Sets, which is known to be NP-complete ( [START_REF] Garey | Computers and intractability[END_REF]).

Exact Cover By 3-Sets (X3C)

Input: A set X of elements with |X| = 3m and a collection C of 3-elements subsets of X where each element appears in exactly 3 sets. Question: Does C contain an exact cover for X, i.e. a subcollection C ⊆ C such that every element occurs in exactly one member set of C ? Remark 2. Note that |C| = 3m and we can suppose that m is even and larger than 6. If m is odd, we consider the instance I even defined as follows: X even = X ∪ {x | x ∈ X} and C even = C ∪ {c x y z | c xyz ∈ C}, and thus in the new instance I even the set has 6m elements and the collection has 6m 3-elements subsets.

We define a polynomial-time reduction and then prove the NP-hardness of Anonymous-Edge-Rotation.

Reduction. Let I = (X, C) be an instance of X3C with |X| = |C| = 3m and m even and q ≥ 3 a given constant. We describe the construction σ transforming an instance I into the graph G := σ(I) where G = (V, E) is defined as follows:

• For each element x ∈ X, we add a vertex v x to the set V elem ⊂ V and a vertex u x to the set V hub ⊂ V .

• For each 3-element set {x, y, z} of the collection C, we add 4 vertices c 1 xyz , c 2 xyz , c 3 xyz and c 4 xyz to the set V set ⊂ V .

• For each i ∈ {1, . . . , 5m} we add a vertex w i to the set V reg ⊂ V and for each j ∈ {1, . . . , 10m} we add a vertex t j to V single ⊂ V .

Let V -= V elem ∪V hub ∪V set ∪V reg ∪V single and |V -| = 3m+3m+12m+15m = 33m. If q = 3, then let V = V -. If q ≥ 4, then for each i, 4 ≤ i ≤ q, add a set of 11m vertices denoted

V i dummy . Let V dummy = V 4 dummy ∪ • • • ∪ V q dummy and define V = V -∪ V dummy . Obviously, |V | = 33m + (q -3)11m.
Now we define the set E of the edges in G.

• For all x, y ∈ X, such that x = y, we add the edge v x u y between the vertex v x ∈ V elem and u y ∈ V hub , to E X ⊂ E.

• For each 3-element set {x, y, z} of the collection C, ∀i ∈ {1, 2, 3, 4}, we add the edges c i xyz u x , c i xyz u y and c i xyz u z to the set E C ⊂ E.

• We add the set of edges E ⊂ E to the vertex set V elem such that (V elem , E ) is a 11-regular graph. Since the number of vertices in the set |V elem | = 3m is even (m is even) and 11 < 3m such a regular graph exists [START_REF] Tomescu | Problems in combinatorics and graph theory[END_REF]. Furthermore, such a graph can be constructed in polynomial time using Havel-Hakimi algorithm [START_REF] Hakimi | On realizability of a set of integers as degrees of the vertices of a linear graph[END_REF].

• We add the set of the edges E ⊂ E to the vertex set V reg such that (V reg , E ) is a (3m + 11)-regular graph. Since the number of vertices of V reg is even and 3m + 11 < 5m, similarly to the previous case such a regular graph exists and can be constructed in polynomial time.

Finally, let

E -= E X ∪ E C ∪ E ∪ E . If q = 3, then let E = E -. If q ≥ 4, then
the set E contains E -and for any i, such that 4 ≤ i ≤ q, we add the set of edges E i dummy ⊆ E to the vertex set V i dummy such that (V i dummy , E i dummy ) is a (9m + 12)-regular. Since the number of vertices of V i dummy is even (m is even) and 9m + 12 ≤ 11m, similarly to the previous case such a regular graph exists and can be constructed in polynomial time.

Obviously, the graph G = (V, E) has the following properties: (i) 10m vertices of degree 0 (the vertices of the set V single ), (ii) 12m vertices of degree 3 (the vertices of the set V set ), (iii) 8m vertices of degree 3m + 11 (the vertices of the set V reg and V hub ), (iv) 3m vertices of degree 3m + 10 (the vertices of the set V elem ), (v) (q -3)11m vertices of degree (9m + 12) (the vertices of the set V dummy ).

Example. Figure 7 represents the transformation σ for q = 3. Let I 1 be the following instance of X3C: m = 2, X = {1, 2, 3, 4, 5, 6}, and C = {{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 6}, {1, 5, 6}, {1, 2, 6}}. To simplify the figure, we only consider m = 2, but for the construction m must be at least 6 (due to an (3m + 11)-regular graph on the vertex set of V reg ). where n is the order of the graph G for an input instance (G, k, r) and q is a fixed number greater than or equal to 3.

v 1 v 2 v 3 v 4 v 5 v 6 u 1 u 2 u 3 u 4 u 5 u 6 c 1 123 c 1 234 c 1 345 c 1 456 c 1 156 c 1 126 c 2 xyz c 3 xyz c 4 xyz t j w i Non-edge V hub V set V elem V single V reg
Proof. Let C ⊆ C be an exact cover for X of size m. Now we define 3m rotations which are independent from each other : for every 3-element set {x, y, z} ∈ C , we replace the edge u x c 1 xyz by the edge u x v x , and similarly u y c 1 xyz by u y v y and u z c 1 xyz by u z v z . Since C is of size m, we define exactly 3m rotations. Let G be the graph obtained from G after applying all 3m rotations. Since C is an exact cover of size m: (i) there are m vertices of type c 1 xyz that lost all 3 neighbours and become of degree 0 in G , (ii) all 3m vertices of type v x are attached to a new neighbour, so they become of degree 3m + 11 in G .

Then G has 10m + m = 11m vertices of degree 0, 12m -m = 11m of degree 3 vertices, 8m + 3m = 11m of degree 3m + 11 vertices and it contains q -3 disconnected (9m + 12)-regular subgraphs of size 11m, hence we conclude that G is the 11m-anonymous graph.

Let I be a yes-instance of Anonymous-Edge-Rotation. Then there exists a sequence of 3m rotations such that the graph G = (V, E ) obtained after applying the rotations to G is a 11m-anonymous graph. Since |V | = 33m + (q -3)11m, there must be only q different degrees classes in G . Note that with one rotation, we can change the degree of two vertices, therefore the degree at most 6m vertices can be changed by 3m rotations. Since the graph G has more than 6m vertices of the degrees 3m + 11, 3, 0 and 9m + 12, all these degree classes must be in G . Furthermore, due to the number of vertices of G, these are the only degree classes in G . This means that in G the number of vertices of degree 3m + 11 must be increased by 3m, the number of vertices of degree 0 must be increased by m, the number of vertices of degree 3 must be decreased by m, there are no vertices of degrees 3m + 10 in G and the other degree classes keep the same amount of vertices.

A single rotation can increase or decrease the degree of a vertex by 1 therefore using 3m rotations no vertex of degree 3m + 10 in G can have degree 0 in G and similarly, no vertex of degree 3 in G can have degree 3m+11 in G . Therefore the 3m new vertices of degree 3m + 11 in G must have degree 3m + 10 in G. This is only possible if the degree of each vertex v x from the set V elem is increased by 1. Similarly, the m new vertices of degree 0 in G must have degree 3 in G, let C G be the set of such vertices. Obviously, C G must be a subset of V set , in which the vertices have the form c xyz with x, y, z ∈ X, for any set {x, y, z} ∈ C, and ∈ {1, 2, 3, 4}. For the same reasons, vertices of degree greater than 9m + 12 cannot be degree less than 3m + 12.

To reach the requested degree configuration in G with exactly 3m edge rotations, in each rotation the degree of each vertex from V elem must be increased by 1 and the degree of each vertex from the set C G must be decrease by 1. To achieve that, for each vertex v x from V elem , the only possible rotation is to add the edge u x v x where u x ∈ V hub and remove the edge u x c xyz where c xyz ∈ C G . To fulfil the condition about the degree classes and the number of the rotations, the only way to achieve that is that C = {{x, y, z} | c xyz ∈ C G } is an exact cover of X.

Characterization of the "closest" k-anonymous degree sequence

In this section we suppose that (G, k) is a feasible instance. For any such instance we define a k-anonymous degree sequence S bound that can be computed in polynomial time if k = θ(n). We show that with the (+1, -1)-degree modifications (Remark 1) the graph G can be transformed into a k-degree-anonymous graph G with degree sequence S bound using at most double of edge rotations as in an optimal solution of Min Anonymous-Edge-Rotation for (G, k).

Note that in general a (+1, -1)-degree modification doesn't correspond to an edge rotation, but as we show later in Section 7.1, it is true for trees. Now in the following steps we show how to define the degree sequence S bound .

Step 1: Compute every available target sequence.

Let S = (s 1 , . . . , s n ) be a non-increasing sequence of non-negative integers, r ∈ {1, . . . , n}. Any partition of S into r contiguous subsequences (i.e. if S[a] and S[b] are in one part, then all S[i], a ≤ i ≤ b must be in the same part) is called a contiguous r-partition. The number of contiguous r-partitions of S is n-1 r-1 , therefore bounded by (n -1) r-1 . Then the number of contiguous partitions of S with at most r parts can be bounded by

r-1 i=0 (n -1) i ≤ 2n r-1 .
For each contiguous -partition p, 1 ≤ ≤ r, we use notation p = [p 1 , . . . , p ], where p i denotes the number of elements in part i, 1 ≤ i ≤ . Note that at this stage important is the number of elements in each part, not which elements from S are in it.

Let G be a graph of order n and k an integer, k ≥ 2. If G is a k-degreeanonymous graph, then the vertices of G can be partitioned into at most c = n k parts where the vertices in each part have the same degree. Let P be the set of all such contiguous partitions with at most c parts. As it follows from the initial discussion, the number of such partitions is bounded by 2n For each contiguous partition p with parts, 1 ≤ ≤ c, there are at most n possibilities for a degree on each position. The test whether the generated sequence is graphic and k-anonymous can be done in O(n) operations. Since |P | = O(n c-1 ), there are at most O(n c-1 × n × n) ≤ O(n 2c ) operations to compute all feasible degree sequences of every partition, where c = n k . Obviously, if c is a constant, such number of operations is polynomial.

Step 2: Find the best one. Now based on the previous analysis we can define the degree sequence S bound and prove some basic properties. for a graph, we can define a k-anonymous sequence S T bound for a tree. The only difference is that in the set Pp , every feasible solution must have d i ≥ 1, which would be a subset of Pp . Also for the testing, we don't need to check whether S is graphic, the condition i=1 p i d i = 2|E|, is enough for the degree sequence of a tree. Lemma 1. Let S be a n-sequence of non-negative integers and denote by S the sequence S sorted in non-increasing order. Let S s be another n-sequence of non-negative integers sorted in non-increasing order. Then

n i=1 |S s [i] -S [i]| ≤ n i=1 |S s [i] -S[i]| (3)
Proof. If S is already in non-increasing order then ( 3

A = n i=1 |S s [i] -S[i]| - n i=1 |S s [i] -S 1 [i]| = |S s [a] -S[a]| -|S s [a] -S 1 [a]| + |S s [b] -S[b]| -|S s [b] -S 1 [b]| = |S s [a] -S 1 [b]| -|S s [a] -S 1 [a]| + |S s [b] -S 1 [a]| -|S s [b] -S 1 [b]|
In order to follow easier six different cases, let

x 1 = S s [a], x 2 = S s [b], x 3 = S 1 [a], x 4 = S 1 [b], and thus A = |x 1 -x 4 | -|x 1 -x 3 | + |x 2 -x 3 | -|x 2 -x 4 |.
Following our assumptions x 1 ≥ x 2 and x 3 > x 4 . Now for all possible arrangements of x 1 , x 2 , x 3 , x 4 we discuss the value A:

• x 1 ≥ x 2 ≥ x 3 > x 4 : A = x 1 -x 4 -x 1 + x 3 + x 2 -x 3 -x 2 + x 4 = 0 • x 3 > x 4 ≥ x 1 ≥ x 2 : A = x 4 -x 1 -x 3 + x 1 + x 3 -x 2 -x 4 + x 2 = 0 • x 1 ≥ x 3 > x 4 ≥ x 2 : A = x 1 -x 4 -x 1 +x 3 +x 3 -x 2 -x 4 +x 2 = 2x 3 -2x 4 > 0 • x 3 ≥ x 1 ≥ x 2 ≥ x 4 : A = x 1 -x 4 -x 3 +x 1 +x 3 -x 2 -x 2 +x 4 = 2x 1 -2x 2 ≥ 0 • x 1 ≥ x 3 ≥ x 2 ≥ x 4 : A = x 1 -x 4 -x 1 +x 3 -x 2 -x 1 -x 2 +x 4 = 2x 3 -2x 2 ≥ 0 • x 3 ≥ x 1 ≥ x 4 ≥ x 2 : A = x 1 -x 4 -x 3 +x 1 +x 3 -x 2 -x 4 +x 2 = 2x 1 -2x 4 ≥ 0
We can conclude that in all cases A ≥ 0, therefore

n i=1 |S s [i] -S 1 [i]| ≤ n i=1 |S s [i] -S[i]|.
If the sequence S 1 is still not in non-increasing order, we can repeat the process of swapping for the next two unsorted elements on S 1 until we obtain the non-increasing sequence S . Each process can be repeated independently, therefore

n i=1 |S s [i] -S [i]| ≤ n i=1 |S s [i] -S[i]|.
Theorem 5. Let (G, k) be a feasible instance for the Min Anonymous-Edge-Rotation problem. Let OPT be an optimum solution that is a minimum set of rotations that transform G to a k-degree-anonymous graph G . Then

n i=1 |S G [i]- S bound [i]| ≤ 2|OP T |,
where the degree sequence S bound is defined in Definition 5.

Proof. Let S G be the degree sequence of G sorted in the same order as S G (i.e. for every

v ∈ V , if deg G (v) is in the position i in S G then deg G (v) is in the position i in S G )
. Let S G be the degree sequence S G sorted in non-increasing order. As in the definition of S bound we considered all the options, there must exist p ∈ P and S ∈ Pp such that S = S G , and

n i=1 |S G [i] -S bound [i]| ≤ n i=1 |S G [i] -S G [i]|.
Since the degree sequence S G is sorted in non-increasing order, then

n i=1 |S G [i] -S G [i]| ≤ n i=1 |S G [i] -S G [i]|
by Lemma 1. One rotation from the graph G j to G j+1 in the sequence of the graphs from G to G can only decrease the degree of a vertex by one and increase the degree of another one by one, hence

n i=1 |S Gj [i] -S G [i]| ≤ n i=1 |S Gj+1 [i] - S G [i]| +

Approximation of Min Anonymous-Edge-Rotation

In this section we show that under some constraints on the number of edges and k, there exists a polynomial time 2-approximation algorithm for the Min Anonymous-Edge-Rotation problem for all feasible inputs (G, k). . It can be shown that

n i=1 (x i -A) 2 ≤ n i=1 (x i -A 0 ) 2 ≤ nR 2 4 , hence σ(S) ≤ R 2 .
The mean absolute derivation of S is defined as

MAD[S] = 1 n n i=1 |x i -A|.
It is well known (e.g. applying Jensen's inequality) that MAD[S] ≤ σ(S).

Based on the correlation mentioned in Remark 4, we calculate an upper bound on the values in the degree sequence S bound in the following lemma. Hence

n i=1 |S G [i] -D[i]| ≤ n i=1 max(|S G [i] -A + 2 |, |S G [i] -A -1 |) ≤ n i=1 |S G [i] -A| + n i=1 2 = nM AD[S G ] + 2n ≤ nσ[S G ] + 2n ≤ n ∆ 2 + 2n = n(∆ + 4) 2
Let ∆ be the maximum value of S bound . If ∆ ≤ ∆, then the condition from Lemma holds. If ∆ > ∆, then the distance between the k first elements of S bound and the k first elements of S G is at least k(∆ -∆) since S bound is k-anonymous and sorted in non-increasing order. Because

n i=1 S bound [i] = n i=1 S G [i],
if the value of some elements is increased of a certain amount, the value of some others have to be decreased by the same amount, so

n i=1 |S G [i] - S bound [i]| ≥ 2k(∆ -∆). If ∆ > (1 + n 4k + n k∆ )∆ then n i=1 |S G [i] -S bound [i]| > 2k( n 4k + n k∆ )∆ = n(∆+4) 2 ≥ n i=1 |S G [i]-D[i]|,
which is not possible due to minimality of S bound .

In the following two lemmas we prove that if a graph has 'sufficiently' many edges than edge rotations with the specific properties exist in a graph. Lemma 3. Let G = (V, E) be a graph with |E| > ∆ 2 , let uv ∈ E. Then there exists an edge ab ∈ E such that both vertices a and b are different from u and v and at most one of the following edges {av, au, bv, bu} is in E.

Proof. For an edge xy ∈ E, let N x = N G (x) \ {y} and N y = N G (y) \ {x}. For a contradiction suppose there exists an edge uv ∈ E such that for every edge ab ∈ E \ (Inc(u) ∪ Inc(v)) at least two of the edges {av, au, bv, bu} are in E. Then at least one vertex from {a, b} is incident to both vertices u, v, hence belongs to N u ∩ N v , or both vertices {a, b} are in

(N u ∪ N v ) \ (N u ∩ N v ). Moreover, every vertex in N u ∪ N v has at most ∆ -1 neighbours in V \ {u, v}. Hence, |E \ (Inc(u) ∪ Inc(v))| ≤ (∆ -1) × (|N u ∩ N v | + |(N u ∪ N v ) \ (N u ∩ N v )| 2 ) = (∆ -1) × |N u ∩ N v | + |N u ∪ N v )| 2 = (∆ -1) × |N u | + |N v | 2 ≤ (∆ -1) 2 Then |E| ≤ |Inc(u) ∪ Inc(v)| + |E \ (Inc(u) ∪ Inc(v))| ≤ 1 + 2(∆ -1) + (∆ - 1) 2 = ∆ 2 . This is in contradiction with hypothesis |E| > ∆ 2 . Lemma 4. Let G = (V, E) be a graph and suppose |E| > ∆ 2 . Let v + , v -∈ V such that 1 ≤ d G (v -) ≤ ∆ and 0 ≤ d G (v + ) ≤ ∆ < |V | -1.
Then there exists a sequence of at most two edge rotations that transform G to G such that Proof. Case 1: Suppose there exists a vertex v ∈ V such that v ∈ N G (v -) and v / ∈ N G (v + ). Let G be the graph obtained from G removing the edge v -v and adding the edge vv + , hence using rotation (vv -, vv + ). Obviously,

d G (v + ) = d G (v + ) + 1, d G (v -) = d G (v -) -
d G (v + ) = d G (v + ) + 1, d G (v -) = d G (v -) - 1
and G is obtained by using a single rotation. Case 2 : N (v -) ⊆ N (v + ). Let u ∈ N G (v -). Since |E| > ∆ 2 and uv + ∈ E, by using Lemma 3 then there exists an edge ab ∈ E such that at most one edge of the set {av + , au, bv + , bu} is in E. If au is in E, then the graph G obtained by two rotations (ab, av + ) and (uv -, ub) has the required properties. If av + is in E, then the graph G obtained by two rotations (ba, bv + ) and (uv -, ua) has the required properties. The remaining two cases if bu or bv + are from E are symmetrical to the above cases, it is enough to swap a and b.

Obviously, such an edge ab can be found in O(|E| 2 ).

Theorem 6. The Min Anonymous-Edge-Rotation problem is polynomial time 2-approximable for all instances (G, k), k ≤ n 4 where k = θ(n) and G is the graph with n vertices and m edges, where max{ n 2 , (1

+ n 4k + n k∆ ) 2 ∆ 2 } ≤ m ≤ n(n-3) 2
, and the constant c is defined as c = n k . Proof. Let (G = (V, E), k) be an instance of Min Anonymous-Edge-Rotation and S G be the degree sequence of G. Let the constant c be defined as c = n k . Due to our assumptions about the number of edges and k, all such instances are feasible as follows from Section 3. First we compute a k-anonymous degree sequence S bound following Definition 5 in O(n 2c ) steps. Due to the assumption k = θ(n) and consequently c being a constant, such number of steps is polynomial. Furthermore, the condition on the number of edges ensures that we can always apply Lemma 4 and find suitable edge rotations.

If there exist two vertices v

+ , v -∈ V such that 0 ≤ S G [v + ] < S bound [v + ] ≤ (1 + n 4k + n k∆ )∆ < |V | -1 and S G [v -] > S bound [v -] we apply Lemma 4 to transform G to a graph G 1 with at most two rotations such that d G1 (v + ) = d G (v + ) + 1 and d G1 (v -) = d G (v -) -1.
We'll be executing the above transformations while there are two vertices v + , v -∈ V with the required properties. In each such transformation we decrease the degree of one vertex by 1 and increase the degree of another one by 1 with at most two rotations. Hence we transform G to a final graph G with degree sequence S bound by at most Finally, since S bound is k-anonymous, G is a k-degree-anonymous graph.

Polynomial cases for Min Anonymous-Edge-Rotation

As follows from Section 4, the Min Anonymous-Edge-Rotation problem is NP-hard even for k = n q and q ≥ 3 is a fixed constant where n is the order of an input graph. In this section we show that the problem can be solved in polynomial time on trees when k = θ(n) or in case of any graph when k = n.

Trees

For a tree T = (V, E) rooted in a vertex r, for any v ∈ V , v = r, child(v) is a vertex that is a neighbor of v not on the path from r to v. Lemma 5. Let T = (V, E) be a tree and v -, v + vertices from V such that v -is not a leaf and v + is not a universal vertex. Then using one rotation we can transform T into a tree T such that d T (v -) = d T (v -) -1 and d T (v + ) = d T (v + ) + 1.

Proof. Let v + be the root of T . Since v -is not a leaf, there exists a vertex c ∈ child(v -). Since T is a tree, cv + / ∈ E. Therefore we can define the rotation (cv -, cv + ) (see Figure 8). Let T be the graph obtained after a such rotation. Since there is no edge between the subtree of c and other vertices, T is a tree. Obviously, the algorithm runs in polynomial time.

Conclusion

In this paper we initiate the study of the complexity of Min Anonymous-Edge-Rotation problem in which the task is to transform a given graph to a kdegree anonymous graph using a minimum number of edge rotations. As we were able to prove NP-hardness in case where the number of vertices k in each degree class is θ(n), further research could explore stronger hardness results or cases when k is a constant. Our next research step includes relaxation of the condition on the number of the edges in the presented 2-approximation algorithm as well as extension of the graph classes in which the Min Anonymous-Edge-Rotation problem can be solved in polynomial time. As the problem doesn't have a solution for all graphs and all possible values of k, our initial feasibility study covers a large part of instances. The extensions of the results are still possible, in the sense of necessary and sufficient conditions.

Figure 1 :

 1 Figure 1: An edge rotation (uv, uw) from uv to uw

Figure 3 : Case 2 Corollary 1 .

 321 Figure 2: Case 1

2 and n ≥ 4 .

 24 Then there exists a feasible solution for the Min Anonymous-Edge-Rotation problem, hence a k-degree-anonymous graph G ∈ G(n, m), for any k ≤ n 4 . Proof. Let m, n, k be fixed. Any graph G ∈ G(n, m) is a 1-degree-anonymous graph, hence we can suppose k ≥ 2. In the first part of the proof we describe a construction of a k-anonymous sequence D = (d 1 , d 2 , . . . , d n ) with property n i=1 d i = 2m for any m, n, k satisfying the restriction of the theorem. In the second part we show that the sequence D is graphic, hence that the sequence satisfies the conditions (1) and (2) from Section 2. As n i=1 d i = 2m is the condition for a constructed sequence, the property (1) trivially holds. Now we construct three distinct k-anonymous sequences Type 1, 2, 3 of integers based on the values of k and s ≡ 2m mod n. Denote by d the average degree of the graph G defined as d

Figure 6 :

 6 Figure 6: The sequence D 3

Theorem 3 .

 3 Let G ∈ G(n, m) for some positive integers n and m. Then (G, n) is a feasible instance of Min Anonymous-Edge-Rotation if and only if 2m n is an integer.

Figure 7 :

 7 Figure 7: σ(I 1 ) Theorem 4. Anonymous-Edge-Rotation is NP-hard even in case k = n q

  c-1 . Now for each contiguous partition p = [p 1 , p 2 , . . . , p ] ∈ P , ∈ {1, . . . , c}, we compute all non-increasing sequences (d 1 , d 2 , . . . , d ) of integers d i such that 0 ≤ d i < |V |. Let Pp be the set of all feasible k-anonymous degree sequences for p, i.e. S = (d 1 , . . . , d 1 p1-times , d 2 , . . . , d 2 p2-times , . . . , d , . . . , d p -times ) = (d p1 1 , d p2 2 , . . . , d p ) ∈ Pp if and only if i=1 p i d i = 2|E|, S is graphic and k-anonymous.

Definition 5 .

 5 Let G be a graph with the degree sequence S G . Then define S bound for G as a degree sequence for which the sumn i=1 |S G [i] -S[i]| achievesthe minimum for all elements S ∈ Pp and p ∈ P .

Remark 3 .

 3 Similarly to a k-anonymous sequence S bound defined in Definition 5

  ) holds. If not then there exist positive integers a, b such that a < b and S[a] < S[b]. Let S 1 be the sequence defined swapping the values S[a], S[b], hence: S 1 [a] = S[b], S 1 [b] = S[a], and S 1 [i] = S[i] otherwise. We denote

2 .

 2 This means by one rotation the value n i=1 |S G [i] -S G [i] decreases by at most 2. After |OP T | rotations, the last graph G j+1 in the sequence is G , therefore n i=1 |S G [i] -S G [i]| ≤ 2|OP T | and the theorem follows.

Remark 4 . 2 ,

 42 Let S = (x 1 , x 2 , . . . , x n ) be a non-increasing sequence of n nonnegative integers. Denote by R = x 1 -x n , A 0 = x1+xn of S is defined as σ(S) = (xi-A) 2 n

Lemma 2 . 2 , k ≤ n 4 ,

 224 Let (G, k) be an instance of the Min Anonymous-Edge-Rotation problem where G is the graph with n vertices and m edges. Suppose that n 2 ≤ m ≤ n(n-3) and let the constant c be defined as c = n k , hence k = θ(n). Let S bound be the k-anonymous degree sequence associated with G defined following Definition 5. Then for every i, S bound [i] ≤ min{(1+ n 4k + n k∆ )∆, n -1}, 1 ≤ i ≤ n.Proof. Let S G be the degree sequence of G sorted in non-increasing order and D the k-anonymous degree sequence constructed following Theorem 2. Denote the unrounded average degree as A = n i=1 S G [i] n . Then using Remark 4, the standard deviation of S G , σ[S G ] ≤ ∆ 2 , and MAD[S G ] ≤ σ(S G ).

1

 1 and degrees of other vertices in G are not changed. These rotations can be found in O(|E| 2 ) steps.

  n i=1 |S G [i] -S bound [i]| rotations. By Lemma 5 we know that n i=1 |S G [i] -S bound [i]| ≤ 2|OP T |, hence we use at most 2 times the numbers of rotations of an optimal solution. In each transformation loop searching for the vertices v + and v -can be done in time O(n) and searching for an edge ab in time O(m 2 ) (Lemma 3). Due to the modifications in each transformation loop, there can be at most O(n 2 ) loops. Therefore the time complexity is bounded by O(n 2c +n 2 ×m 2 ×n). Since c ≥ 4, O(n 2c +m 2 ×n 3 ) ≤ O(n 2c ).

  Moreover d T (v -) = d T (v -) -1 and d T (v + ) = d T (v + ) + 1.

Figure 8 :Theorem 7 . 2 ≤ n 2 2 ≤

 87222 Figure 8: Transformation T to T

7. 2 . 1 :

 21 One degree class, k = nIn this part we show that Min Anonymous-Edge-Rotation is polynomialtime solvable for instances where k coincides with the number of vertices of the graph, that means all vertices must be in the same degree class.Input : A graph G = (V, E) Output: A sequence S of edge rotations if 2|E| |V | is an integer NO otherwise S = ∅ ; d = 2|E| |V | ; if if d is not integer then return NO ; else while ∃u, v ∈ V such that d G (u) < d and d G (v) > d do Let w ∈ N (v) \ N (u) ; E = E \ {vw}; E = E ∪ {uw}; S = S ∪ {(wv, wu)}; end end Algorithm Algorithm for k = |V |

  = G, G 1 , G 2 , . . . , G such that G i+1 can be obtained from G i by one edge rotation, and G is k-degree-anonymous.

	for any two indices i, j such that
	i, j ∈ {1, . . . , n}. Note that each edge rotation corresponds to a (+1, -1)-degree
	modification, but not opposite.
	Definition 4. A sequence of integers D = (d 1 , d 2 , . . . , d n ) is called k-anonymous
	where k ∈ {1, . . . , n}, if for each element d i from D there are at least k -1 other
	elements in D with the same value. A graph G is called k-degree-anonymous
	if its degree sequence is k-anonymous. The vertices of the same degree corre-
	spond to a degree class.
	In this paper we study the following anonymization problem:
	Min Anonymous-Edge-Rotation
	Input: (G, k) where G = (V, E) is an undirected graph and k a positive
	integer, k ∈ {1, . . . , |V |}.
	Output: If there is a solution, find a sequence of a minimum number + 1
	of graphs G 0

1 , . . . , d n ) in such a way that d i := d i + 1, d j := d j -1

 Lemma 6. Let G = (V, E) be a graph and u, v ∈ V . If N G (u) N G (v), then there is an edge rotation that leads to a graph G such that d G (u) = d G (u) -1 and d G (v) = d G (v) + 1.

Proof. Since N G (u) N G (v), there exists w ∈ V such that uw ∈ E and vw / ∈ E. Then we can do the following edge rotation (uw, vw) and get the graph G with E = (E \ {uw}) ∪ {vw}.

Lemma 7. Let (G, n) be an instance of Min Anonymous-Edge-Rotation where G ∈ G(n, m) for some positive integers m, n, and 2m

n is an integer. Then the optimum value of Min Anonymous-Edge-Rotation on (G, n) is

n . By Remark 5, there is an edge rotation that leads to a graph

rotations are necessary to have all the vertices of the same degree 2m n , therefore the optimum value of Min Anonymous-Edge-Rotation on the instance (G, n) is at least w∈V |d G (w)-2m/n| 2 . Now suppose that the optimum value is r strictly less than w∈V |d G (w)-2m/n| 2 . Each rotation increases the degree of a vertex by one and decreases the degree of another vertex by one too. Obviously, each vertex w has to be involved in at least |d G (w) -2m/n| edge rotations to reach the degree 2m n . Hence if there are r < w∈V |d G (w)-2m/n| 2 edge rotations then in any graph G obtained from G using r edge rotations there exists w ∈

n . Theorem 8. The Min Anonymous-Edge-Rotation problem is polynomialtime solvable for instances (G, k) when k = n, where n is the order of the graph G.

Proof. In case k = n, we are looking for a n-degree-anonymous graph with only one degree class, hence for a regular graph. Due to Theorem 3, we can easily decide whether (G, n) is a feasible instance of Min Anonymous-Edge-Rotation: if for G ∈ G(n, m) the fraction 2m n is not an integer, (G, n) is not a feasible input.

For a feasible input (G, n), the result is based on Algorithm 1 and its correctness follows from Lemmas 6 and 7.

Declaration of interests

☒ The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

☐The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: Cristina Bazgan Pierre Cazals Janka Chlebikova


Floriane Remy Msc

DDS b Pierre Bonnaure

MD c Philippe Moisdon

Philippe Burgart Msc

Yves Godio-Raboutet Msc

PhD Lionel Thollon

MD Laurent Guyot

Floriane Remy
email: floriane.remy.ymd@gmail.com

Preliminary results on the impact of simultaneous palatal expansion and mandibular advancement on the respiratory status recorded during sleep in OSAS

Keywords: Maxillary expansion, Mandibular advancement, Custom-made oral appliance, Child, Obstructive Sleep Apnea, Sleep study

la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Obstructive Sleep Apnea Syndrome (OSAS) is a respiratory disorder characterized by a partial or complete obstruction of the upper airways during sleep (respectively apnea or hypopnea). Its prevalence within the pediatric population ranges between 1% and 5% [START_REF] Marcus | Diagnosis and Management of Childhood Obstructive Sleep Apnea Syndrome[END_REF].

Because of this abnormal ventilation, this disorder leads to an oxygen desaturation and a sleep fragmentation and is associated with various signs and symptoms as snoring, excessive daytime sleepiness, reduced concentration, hypertension or even cardiac arrhythmia [START_REF] Marcus | Diagnosis and Management of Childhood Obstructive Sleep Apnea Syndrome[END_REF]. Its early management and resolution are therefore important for the healthy development of the child.

Several factors should be considered to choose the more efficient therapeutic strategy: the etiology of the obstruction, its degree of severity and the patient's compliance to undergo continuous treatment. Among the therapies available, the adenotonsillectomy presents good short-term results but several cases of recurrence were reported, especially in children with an underdeveloped maxilla or a retrusive mandible [START_REF] Guilleminault | Sleep disordered breathing: surgical outcomes in prepubertal children[END_REF]. Even though less invasive, the Continuous Positive Air Pressure (CPAP) technique outcomes depend on the obstruction severity and the child's compliance [START_REF] Lynch | Quality of Life in Youth With Obstructive Sleep Apnea Syndrome (OSAS) Treated With Continuous Positive Airway Pressure (CPAP) Therapy[END_REF].

Constricted maxillary dental arch and a retrusive position of the mandible are considered as common characteristics in the pediatric OSAS [START_REF] Flores-Mir | Craniofacial morphological characteristics in children with obstructive sleep apnea syndrome: a systematic review and meta-analysis[END_REF]. Besides, according to the systematic review of Caron et al., OSAS is associated to a craniofacial anatomy anomaly in 7% to 67% of the pediatric population [START_REF] Caron | Obstructive sleep apnoea in craniofacial microsomia: a systematic review[END_REF]. Indeed, considering their anatomical connections, a posterior displacement of the mandible results in a fall of the tongue in the pharynx and an anteroposterior narrowing of the upper airways [START_REF] Muto | A cephalometric evaluation of the pharyngeal airway space in patients with mandibular retrognathia and prognathia, and normal subjects[END_REF]. Likewise, a narrow palate is associated with an insufficient development of the nasal cavities, so an oral breathing pattern is commonly observed in these patients [START_REF] Baroni | Craniofacial features of subjects with adenoid, tonsillar, or adenotonsillar hypertrophy[END_REF].

Considering these anatomic abnormalities, dentists are in favorable position to identify and help in the management of pediatric OSAS [START_REF] Academy | Oral healt policy on obstructive sleep apnea[END_REF]. Besides, oral appliances have been widely used in adults, with great amount of success [START_REF] Ramar | Clinical Practice Guideline for the Treatment of Obstructive Sleep Apnea and Snoring with Oral Appliance Therapy: An Update for 2015[END_REF]. Among the various designs of oral appliances, rapid maxillary expanders and mandibular advancement devices improve the upper airways patency and relieve their obstruction: by widening the palatal vault and the nasal cavities, by moving the tongue outside the pharynx, by changing hyoid bone position or by modifying airways dimensions. Even though the effects of these techniques on the oral space have already been observed [START_REF] Machado-Júnior | Rapid maxillary expansion and obstructive sleep apnea: A review and meta-analysis[END_REF][START_REF] Noller | Mandibular advancement for pediatric obstructive sleep apnea: A systematic review and meta-analysis[END_REF], very few studies applied them simultaneously [START_REF] Galeotti | Effects of simultaneous palatal expansion and mandibular advancement in a child suffering from OSA[END_REF][START_REF] Rădescu | Effects of rapid palatal expansion (RPE) and twin block mandibular advancement device (MAD) on pharyngeal structures in Class II pediatric patients from Cluj-Napoca, Romania[END_REF].

In the present study, the effects of an innovative custom-made oral device combining these two technics were reported in children with OSAS and Class II malocclusion: this study aimed to demonstrate that simultaneous palatal expansion and mandibular advancement modifies sufficiently the craniofacial anatomy to improve the respiratory status during sleep.

Materials and Methods

The study sample

The study sample was selected from the patients of a French private orthodontic practice who consulted for a Class II malocclusion. Only children who were identified as OSAS during a diagnostic polysomnography prescribed by the orthodontist were selected. OSAS was diagnosed with an Apnea/Hypopnea Index (AHI) ≥1 event per hour of sleep. These children were systematically treated with the personalized innovative oral appliance described below.

Thus, the study sample was composed of 103 children aged between 3 and 12 years (mean ±standard deviation = 7.0 ± 1.8 years old).

According to the French law n°2012-300 of March 5 th , 2012 on researches involving human beings, because this study was retrospective and non-interventional, and because data were anonymized, no signed consent was required. This study was reviewed and approved by the Institutional Review Board of Aix-Marseille University (no. 2019-14-03-001).

The custom-made oral appliance

All children were treated with a personalized innovative oral appliance composed of two thermoformed intra-buccal pieces (Fig. 1) and described as follows:

-The maxilla expander is a hyrax-type screw 13 mm (RMO®, Denver, Colorado) fixed with an imbedded 0.045-inch wire framework on an acrylic maxillary plate (Duran®, Scheu Dental, Iserlohn, Germany) glued to the buccal, lingual and occlusal surfaces of the canine and first and second deciduous molars (with the glue Fuji ORTHO™ LC, GCAmerica, Alsip, Illinois). Activation of the expander screw corresponded to a maxillary arch expansion of about 0.25 mm.

-The mandibular advancement device is a removable acrylic plate (Durasoft®, Scheu Dental, Iserlohn, Germany) which covers all the lower teeth. The device was designed to create an initial maximal jumping, to achieve a normal dental occlusion (Class I occlusion). For two months, this protrusion could be readjusted by the physician according to the achieved outcomes and the child's comfort, with an advancement of 1-2 mm.

-The upper and lower plates could be connected by sliding an embedded 0.045-inch wire framework on the mandibular plate in the embedded acrylic tubes located on the labial side of the maxillary plate. The child's parents were instructed to advance the maxillary expander screw once a night for 20 days and then twice a night for 10 days. During a consultation at the end of these 30 days, the extension rate should have been > 10 mm. If not, new activations were planned; otherwise the patient was instructed to stop activations and to wear the mandibular advancement device, only during night. At this time, the maxillary expander screw remained in the child's mouth for another two months to ensure the calcification of the palatine suture. After these three months (30 days of activations + two months of calcification), the expander screw was deposed whereas the acrylic maxillary plate remained glued to the superior deciduous teeth during the whole treatment period to fix the mandibular advancement device. At this time, a lingual rehabilitation with a speech therapist was also initiated. After approximately nine months of treatment, a functional Class I bite was achieved. At that time, the device (both the lower and upper parts) was removed. This treatment protocol is summarized in Fig. 2 where T0 referred to the initiation of the treatment.

Sleep studies

The respiratory status during sleep was assessed with sleep studies performed with SOMNOlab ® (Weinmann, Hamburg, Germany) at patient's home, at the beginning and at the end of the treatment.

An Apnea/Hypopnea Index (AHI) was defined as the number of apneas and hypopneas events per hours of recorded sleep. In accordance with the reviewed literature, this index was used to assess the severity of the child's OSAS as: mild (1≤ AHI <5), moderate (5≤ AHI <10) or severe (≥10) [START_REF] Álvarez | Documento de consenso del síndrome de apneas-hipopneas durante el sueño en niños (versión completa)[END_REF].

An Oxygen Desaturation Rate (ODR) was defined as the amount of time the blood oxygen saturation was ≤96% over the recorded sleep period. A pediatric OSAS was considered when this rate was >1.4% [START_REF] Álvarez | Documento de consenso del síndrome de apneas-hipopneas durante el sueño en niños (versión completa)[END_REF].

An Arousal Index (AI) was computed as the number of arousals per hour of total sleep time.

An AI ≥11 was considered pathological [START_REF] Goh | Sleep Architecture and Respiratory Disturbances in Children with Obstructive Sleep Apnea[END_REF][START_REF] Scholle | Normative values of polysomnographic parameters in childhood and adolescence: arousal events[END_REF]. This index was classified as respiratory-related (AISRRD) if the arousal occurred immediately after an apnea or hypopnea. If so, a Sleep Respiratory-Related Disorder (SRRD) was identified when the AISRRD was >1 [START_REF] Scholle | Normative values of polysomnographic parameters in childhood and adolescence: arousal events[END_REF][START_REF] Franco | Overnight polysomnography versus respiratory polygraphy in the diagnosis of pediatric obstructive sleep apnea][END_REF].

Likewise, when the arousal occurred together with a series of consecutive leg movements, it was classified as related to a Periodic Limb Movement syndrome (PLM) [START_REF]Atlas Task Force. Recording and scoring leg movements[END_REF]. When this kind of arousals (reported as AIPLM) occurred ≥5 times per hours of recorded sleep, it was considered pathologic [START_REF]The international classification of sleep disorders: diagnostic & coding manual[END_REF].

Finally, the Chervin's French translated pediatric sleep questionnaires were sent to the treated children's parents, 2 to 6 years after the end of the treatment [START_REF] Chervin | Pediatric sleep questionnaire (PSQ): validity and reliability of scales for sleep-disordered breathing, snoring, sleepiness, and behavioral problems[END_REF][START_REF] Chervin | Pediatric sleep questionnaire: prediction of sleep apnea and outcomes[END_REF]. This questionnaire is composed of 22 items which can be answered by Yes / No / Do not know. Parents were asked if they noticed moments of apnea, snoring, mouth breathing, daytime sleepiness or behavioral issues after their child's treatment. According to Chervin et al., a score superior to 8 (i.e. 8 positive answers) demonstrated a reoccurrence of the OSAS symptoms, with a sensibility and a specificity of 85% and 86% respectively [START_REF] Chervin | Pediatric sleep questionnaire (PSQ): validity and reliability of scales for sleep-disordered breathing, snoring, sleepiness, and behavioral problems[END_REF][START_REF] Chervin | Pediatric sleep questionnaire: prediction of sleep apnea and outcomes[END_REF].

Any remarks reported by the parents on their child's sleep quality and feelings during the consultations were also collected.

The statistical analyses

Statistical analyses were performed with RStudio [START_REF] Core | R: A language and environment for statistical computing[END_REF] (version 3.3.2) with a significance threshold fixed at 5%. Data are expressed as means ± standard deviation. The significance of the evolution of the polysomnographic parameters collected pretreatment versus posttreatment was evaluated with Student's T-Tests for paired groups.

Results

The evolution of the polysomnographic data is summarized in Table 1, associated to the Student's T-Tests results assessing the significance of the observed pre-and post-treatment differences.

All children presented a pathological AHI (≥ 1). For 31% of the sample, the OSAS was moderate (5≤ AHI <10) and for 7 children, it was severe (AHI ≥10). After the treatment, the AHI systematically decreased <5, except for 2 children, even though it remains close to it (from 7 to 5.7 and from 8.3 to 5.1 respectively). This index was even <1 for 41% of the sample. Beside this significant decrease of the AHI values, their post-treatment spread was also reduced, assessing a normalization of this parameter.

The desaturation rate also decreased, even though not significantly. However, for majority of the patients, this index did not become inferior to the pathological threshold (ODR < 1.4/h) at the end of the treatment: an improvement was observed for 48% of the sample.

Sleep became less fragmented following the treatment: for 76% of the sample, the AI decreased <11. This improvement of the sleep quality was more particularly characterized by the significant diminution and normalization of the SRRD (AISRRD <1). However, the PLM syndrome did not evolve for 82% of the sample. The AIPLM even increased ≥5 for 22% of the sample.

Finally, 75 of the 103 treated children answered to the questionnaires (i.e. 73% of the total study sample). These results are summarized in Table 2. The mean score of the questionnaire was 4.16.

Among these 75 children, only 12 (16%) had a final score superior to 8, marking a reoccurrence of the OSAS symptoms. In more than half of the cases (68%), parents answer YES to the question n°10, reporting behavior problems with easy distraction and a child generally excited. For almost 50% of the cases, parents also reported that, despite of the treatment, their child trend to have an oral breathing (question n°3).

The biggest number of "Do Not Know" answers (around 20%) has been counted for the questions referring to the apneic event observed during sleep (question n°2) and to the oral or nasal breathing mode of the child (question n°3).

Discussion

The present study demonstrated that the simultaneous rapid maxilla expansion and nocturne mandibular advancement effectively modified the oral space in the three spatial dimensions (Fig. 3) associated with a significant improvement of the sleep breathing quality. A significant increase in the oropharyngeal space was also observed after the treatment. As cephalometric changes induced by such treatment strategy has already been described in the literature, they will not be discussed here [START_REF] Galeotti | Effects of simultaneous palatal expansion and mandibular advancement in a child suffering from OSA[END_REF][START_REF] Rădescu | Effects of rapid palatal expansion (RPE) and twin block mandibular advancement device (MAD) on pharyngeal structures in Class II pediatric patients from Cluj-Napoca, Romania[END_REF].

Indeed, all the collected polysomnographic parameters, which assess the severity of the OSAS symptoms, decreased following the orthopedic treatment. This decrease was even significant for the main pathologic criteria: the AHI which decreased ≤ 5 for 98% of the sample.

Moreover, there was a complete recovery (AHI < 1, ODR <1.4/h and AISRRD < 1) for 14% of the sample. This significant diminution of the AHI at the end of an orthodontic treatment was already observed by Villa et al. who performed during 12 months a rapid maxillary expansion therapy on 40 patients aged between 4-10 years old and initially showing clinical signs of malocclusion and an AHI >1 [START_REF] Villa | Rapid maxillary expansion outcomes in treatment of obstructive sleep apnea in children[END_REF]. In the present study, the same outcomes were obtained with a shorter treatment period: 9 months. This short length of intervention may be explained by the early treatment intervention, when the bone is plastic, and growth is maximal. In another study on an oral jaw-positioning appliance for the management of 32 OSAS children with clinical signs of dysgnathia, Villa et al. [START_REF] Villa | Randomized controlled study of an oral jaw-positioning appliance for the treatment of obstructive sleep apnea in children with malocclusion[END_REF] also reported a decrease of at least 50% in the AHI for 64% of the sample. According to this definition, the custom-made oral device used in the present study achieved a better success rate of 79%. This demonstrate the importance of the combination of two effective technics (rapid maxillary expansion and nocturnal mandibular advancement) so their effects are optimized.

Few months after the end of the treatment, 59% of the treated children presented a residual OSAS with an AHI which remained >1. Pirelli et al. [START_REF] Pirelli | Rapid maxillary expansion in children with obstructive sleep apnea syndrome[END_REF], who also performed a 4-months rapid maxillary expansion on 31 OSAS children, get for their part a systematic decrease of the AHI <1. However, their sample included children showing orofacial anomalies restricted to the maxilla whereas the present study analyzed children with Class II malocclusion. Associated to this significant decrease of the AHI, a significant improvement of the sleep quality was also noticed, which was less fragmented: most particularly, there was a significant decrease of the arousals related to respiratory disorders (AISRRD). The oxygen desaturation rate (ODR) and the global arousal index (AI) also decreased below the pathological threshold (<1.4 and <11 respectively) for 48% and 76% of the sample respectively. However, arousals related to Periodic Leg Movements (AIPLM) were still omnipresent following the treatment.

As suggested by several authors, this emphasizes the importance to identify the cause of airways obstruction: the pathophysiology of the pediatric OSAS is complex, the respiratory disorders being induced by a combination of factors [START_REF] Woodson | Physiology of sleep disordered breathing[END_REF].

Despite this significant improvement of the respiratory status during sleep, demonstrated with the significant decrease of both the AHI and AISRRD, the sleep quality was not totally restored. Indeed, even though the ODR and the AI did decrease after the treatment, this decrease was not significant. Nevertheless, parents reported during the consultations an immediate improvement of the sleep quality of their child. These results may highlight the importance of a long-term follow-up as an improvement of the pediatric OSAS symptoms may not appears as soon as few months after the end of the treatment: normal cephalometric growth recovery is a slow process. Besides, according to pediatric sleep questionnaires results, only 17% of the present study sample showed a reoccurrence of the OSAS symptoms several years after the end of the treatment.

Thus, these outcomes may suggest that when the orofacial anomaly affects both the maxilla and the mandible, the normal ventilation could be progressively and permanently restored. It also highlights the importance of the intervention of a multidisciplinary team in the management of pediatric OSAS. Longitudinal studies should still be performed to observe the evolution of the quantitative sleep parameters several years after the end of the treatment. This significant improvement of OSAS symptoms through the simultaneous maxillary expansion and mandibular advancement has been already observed [START_REF] Galeotti | Effects of simultaneous palatal expansion and mandibular advancement in a child suffering from OSA[END_REF][START_REF] Rădescu | Effects of rapid palatal expansion (RPE) and twin block mandibular advancement device (MAD) on pharyngeal structures in Class II pediatric patients from Cluj-Napoca, Romania[END_REF]. However, their samples were smaller than the sample of the present study and were mainly focused on the cephalometric effects of the orthopedic treatment.

The present study did not include a control group of untreated subjects with Class II malocclusion and OSAS: because of the ethical concern of not treating patients during their pubertal growth spurt. Indeed, not treating OSAS children may results in various problems as behavioral disorders or serious morbidities as growth failure, cor pulmonale, hypertension … [START_REF] Chang | Obstructive sleep apnea syndrome in children: Epidemiology, pathophysiology, diagnosis and sequelae[END_REF]. However, considering the literature, the authors may assert the real impact of this therapeutic strategy. Indeed, Pavoni et al. observed more significant changes in mandibular length, airways dimensions or hyoid and tongue position in children treated with an resolution of OSAS symptoms, Chervin et al. observed it for for 42% of the 5 to 9 years old children included in the ChildHood Adenotonsillectomy Trial (CHAT), but without defining the cephalometric status of these children [START_REF] Chervin | Prognosis for Spontaneous Resolution of OSA in Children[END_REF].

Finally, this innovative therapeutic strategy, used at an early stage of the child's growth and associated with myofunctional rehabilitation exercises, significantly increased the OSAS child's oral space in the three spatial dimensions. Moreover, the present outcomes suggest the effectiveness of the custom-made oral appliance for OSAS children management since it prevents airflow obstruction by enlarging the upper airways, and by promoting the lingual advancement during the night. These results are in accordance with previous studies investigating a similar therapeutic strategy [START_REF] Galeotti | Effects of simultaneous palatal expansion and mandibular advancement in a child suffering from OSA[END_REF][START_REF] Rădescu | Effects of rapid palatal expansion (RPE) and twin block mandibular advancement device (MAD) on pharyngeal structures in Class II pediatric patients from Cluj-Napoca, Romania[END_REF]. Thus, simultaneously treating OSAS children with a rapid maxillary expansion and a nocturne mandibular advancement should be recommended.

Table 1

Mean and standard deviation of the polysomnographic parameters collected before and after the treatment, associated to the Student's T-Tests p.value assessing the significance of the differences. Shaded cases correspond to p.values < 5%

Parameter

Figures caption:Fig. 1 Fig. 2 Fig. 3

 123 Figures caption:

Funding

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

Declaration of Interest Statement

The authors report no conflict of interest.

Ethical approval

According to the French law n°2012-300 of March 5 th , 2012 on researches involving human beings, because this study was retrospective and non-interventional, and because data were anonymized, no signed consent was required. This study was reviewed and approved by the Institutional Review Board of Aix-Marseille University (no. 2019-14-03-001).

Table 2

Summary of the replies to the post-treatment pediatric sleep questionnaires, as perceived by the parents (for more information about the questions, please refer to the article of Chervin


Roger Ohayon

Roger Valid Symmetric

Keywords: