Frédéric Havet

Dorian Mazauric

Viet-Ha Nguyen

Rémi Watrigant

Overlaying a hypergraph with a graph with bounded maximum degree

Keywords: graphs, hypergraphs, complexity, algorithm, computational structural biology

Let G and H be respectively a graph and a hypergraph defined on a same set of vertices, and let F be a fixed graph. We say that G F -overlays a hyperedge S of H if F is a spanning subgraph of the subgraph of G induced by S, and that G F -overlays H if it F -overlays every hyperedge of H. Motivated by structural biology, we study the computational complexity of two problems. The first problem, (∆ ≤ k) F -Overlay, consists in deciding whether there is a graph with maximum degree at most k that F -overlays a given hypergraph H. It is a particular case of the second problem Max (∆ ≤ k) F -Overlay, which takes a hypergraph H and an integer s as input, and consists in deciding whether there is a graph with maximum degree at most k that F -overlays at least s hyperedges of H.

We give a complete polynomial/N P-complete dichotomy for the Max (∆ ≤ k)-F -Overlay problems depending on the pairs (F, k), and establish the complexity of (∆ ≤ k) F -Overlay for many pairs (F, k).

Introduction

A major problem in structural biology is the characterization of low resolution structures of macro-molecular assemblies [? ? ]. To attack this very difficult question, one has to determine the plausible contacts between the subunits (e.g. proteins) of an assembly, given the lists of subunits involved in some complexes. We assume that the composition, in terms of individual subunits, of selected complexes is known. Indeed, a given assembly can be chemically split into complexes by manipulating chemical conditions. This problem can be conveniently modelled by graphs and hypergraphs. We consider the hypergraph H whose vertices represent the subunits and whose hyperedges are the complexes. We are then looking for a graph G with the same vertex set as H whose edges represent the contacts between subunits, and satisfying (i) some local properties for every complex (i.e. hyperedge), and (ii) some other global properties.

For example, consider the following properties: (i) the subset of vertices of every hyperedge must form a connected subgraph of G and (ii) the number of edges of G is at most the number of vertices. The first property comes from the fact that the complexes obtained (e.g. by native mass spectrometry) are connected components of a given assembly. The second property is deduced from the constant number of subunits that are in contact to any subunit of an assembly. It means that the total number of edges is linear in the number of vertices (in our example, we assume that the number of edges is at most the number of vertices). Let us now consider a hypergraph H whose hyperedges are {v 1 , v 2 , v 3 }, {v 2 , v 4 , v 5 }, {v 3 , v 4 , v 5 }, and {v 4 , v 5 , v 6 , v 7 }. These hyperedges are depicted in Figure 1 (left) in which a vertex labeled i represents v i . The graph G described in Figure 1 (right) satisfies the previous properties: the set of vertices {v 4 , v 5 , v 6 , v 7 } induces a connected subgraph (same observation for the three other hyperedges) and the number of edges of G is exactly the number of vertices. We first focus on the local properties. They are usually modelled by a (possibly infinite) family F of admissible graphs to which each complex must belong: to this end, we define the notion of enforcement of a hyperedge and a hypergraph. A graph G F-enforces a hyperedge S ∈ E(H) if the subgraph G[S] of G induced by S belongs to F, and G F-enforces H if G F-enforces all hyperedges of H. Very often, the considered family F is closed on taking edge supergraphs [? ? ]: if F ∈ F, then every graph obtained from G by adding edges is also in F. Such a family is completely defined by its set M = M(F) of minimal graphs that are the elements of F which are not edge supergraphs of any other. In this case, a graph G F-enforcing S is such that there is an element of M which is a spanning subgraph of G [S]. This leads to the following notion of overlayment when considering minimal graph families.

Definition 1. A graph G F-overlays a hyperedge S if there exists F ∈ F such that F is a spanning subgraph of G[S], and G F-overlays H if G Foverlays every hyperedge of H.

As said previously, the graph sought will also have to satisfy some global constraints. Since in a macro-molecular assembly the number of contacts is small, the first natural idea is to look for a graph G with the minimum number of edges. This leads to the min-F-Overlay problem: given a hypergraph In this paper, we consider the variant in which the additional constraint is that G must have a bounded maximum degree: this constraint is motivated by the context of structural biology, since a subunit (e.g. a protein) cannot be connected to many other subunits. This yields the following problem for any family F of graphs and an integer k.

(∆ ≤ k)-F-overlay Input: A hypergraph H. Question: Does there exist a graph G F-overlaying H such that ∆(G) ≤ k ?
We denote by over F (H, G) the number of hyperedges of H that are Foverlaid by G. A natural generalization is to find over F (H, k), the maximum number of hyperedges F-overlaid by a graph with maximum degree at most k.

Max (∆ ≤ k)-F-overlay

Input: A hypergraph H and a positive integer s. Question: Does there exist a graph G such that ∆(G) ≤ k and over F (H, G) ≥ s?

Observe that there is an obvious reduction from (∆ ≤ k)-F-overlay to

Max (∆ ≤ k)-F-overlay (by setting s = |E(H)|).
In this paper, we mainly consider the case when the family F contains a unique graph F . We abbreviate Then, in Section 3, we give a complete polynomial/N P-complete dichotomy for the Max (∆ ≤ k)-F -Overlay problems.

(∆ ≤ k)-{F }-Overlay and Max (∆ ≤ k)- {F }-Overlay to (∆ ≤ k)-F -Overlay and Max (∆ ≤ k)-F -Overlay,
Theorem 2. Max (∆ ≤ k)-F -Overlay is polynomial-time solvable if ei- ther ∆(F ) > k, or F is an anticomplete graph, or F = O 2 , or k = 1 and F = O 3 . Otherwise it is N P-complete.
In Section 4, we investigate the complexity of (∆ ≤ k)-F -Overlay and (∆ ≤ k)-F-Overlay problems. We believe that each such problem is either polynomial-time solvable or N P-complete. However the dichotomy seems to be more complicated than the one for Max (∆ ≤ k)-F -Overlay. We exhibit several pairs (F, k) such that (∆ ≤ k)-F -Overlay is polynomialtime solvable, while Max (∆ ≤ k)-F -Overlay is N P-complete. This is in particular the case when F is a complete graph (Proposition 3), F is connected k-regular (Proposition 4), F is a path and k = 2 (Theorem 7), and when F is the cycle on 4 vertices and k ≤ 3 (Theorem 6).

Most notations of this paper are standard. We now recall some of them, and we refer the reader to [? ] for any undefined terminology. The degree of a vertex v in a graph is denoted by d(v). For a positive integer p, let Let H be a hypergraph. Two hyperedges are adjacent if their intersection has size at least 2. A hypergraph is neat if any two distinct hyperedges intersect in at most one vertex. In other words, a hypergraph is neat if there is no pair of adjacent hyperedges. We denote by K(H), the graph obtained by replacing each hyperedge by a complete graph. In other words,

V (K(H)) = V (H) and E(K(H)) = {xy | ∃S ∈ E(H),

The graphs with one edge

In this section, we establish Theorem 1. Let p ≥ 2, and H be a puniform hypergraph. Consider the edge-weighted graph (K(H), w H ). For every matching M with at least one edge of this graph, let G M = (V (H), M ).

Every hyperedge O p -overlaid by G M is a superset of at least one edge of M and at most p 2 edges of M . We thus have the following:

Observation 1. For every matching M of K(H), we have:

1 p 2 w H (M ) ≤ over Op (H, G M ) ≤ w H (M ), (1)
where w H (M ) = e∈M w H (e).

Consider first the case when p = 2. Let H be a 2-uniform hypergraph.

Every hyperedge is an edge, so

K(H) = H. Moreover, a (hyper)edge of H is O 2 -overlaid by G if and only if it is in E(G). Hence Max (∆ ≤ k)-O 2 -
Overlay is equivalent to finding a maximum k-matching (that is a subgraph with maximum degree at most k) in K(H). This problem is polynomial-time solvable, see [? , Chap. 31], hence:

Proposition 1. Max (∆ ≤ k)-O 2 -Overlay is polynomial-time solvable for
all positive integer k.

If p = 3, Inequalities (1) are equivalent to over O 3 (H, G M ) = w H (M ).
Since the edge set of a graph with maximum degree 1 is a matching, Max (∆ ≤ 1)-O 3 -Overlay is equivalent to finding a maximum-weight matching in the edge-weighted graph (K(H), w H ). This can be done in polynomialtime, see [? ,Chap. 14].

v u v w w w w u B z 1 t 1 1 t 2 1 t 3 1 s 1 1 u 1 v 1 s 2 1 u 4 v4 s 3 1 u 5 v5
Figure 3: The construction of a variable gadget (left) which means that a blue (resp. red) edge in this gadget corresponds to that the variable is true (resp. f alse). And an example of clause gadget of C 1 = (x 1 ∨ x4 ∨ x5 ) (right) with three edges u 1 v 1 , u 4 v4 , u 5 v5 which corresponds to an assignment φ such that φ(x 1 ) = φ(x 4 ) = φ(x 5 ) = true.

Proposition 2. Max (∆ ≤ 1)-O 3 -Overlay is polynomial-time solvable.

We shall now prove that if p ≥ 4, or p = 3 and k ≥ 2, then Max (∆ ≤ k)-O p -Overlay is N P-complete. We prove it by a double induction on k and p. Theorems 3 and 4 first prove the base cases of the induction and Lemma 1 corresponds to the inductive steps.

Theorem 3. (∆ ≤ 1)-O 4 -Overlay is N P-complete.
Proof. We reduce 3-SAT to (∆ ≤ 1)-O 4 -Overlay.

We shall need the following gadget hypergraph J = J(A, B).

V Let Φ be an instance of 3-SAT with m clauses C 1 , . . . , C m on n variables

x 1 , . . . , x n . Let H = H(Φ) be the 4-uniform hypergraph constructed as follows (see Figure 3).

• For each variable x i , we create the variable gadget V G i as follows.

Its vertex set is {u i , v i , vi , w i , wi , w i , w i , u i } ∪ B i , with |B i | = 4. We add the hyperedges of J({u i , v i , vi }, B i ), J({v i , w i , w i }, B i ), J({v i , wi , w i }, B i ),
and J({u i , w i , w i }, B i ).

• For each clause C j = 1 ∨ 2 ∨ 3 , we create the clause hypergraph CG j .

Its vertex set is {z j } ∪ 3 k=1 {s k j , t k j , u k j , v k j }. Set Z j = {t 1 j , t 2 j , t 3 j , z j } and for k ∈ {1, 2, 3}, set T k j = {s k j , t k j , u k j , v k j }. The hyperedge set of CG j is {Z j , T 1 j , T 2 j , T 3 j }.
Then for each k ∈ {1, 2, 3}, we identify u k j and v k j with u i and v i if k = x i and with u i and vi if k = xi .

Let us prove that there is an (O 4 , H, 1)-graph if and only if Φ is satisfiable.

The general idea of the proof is that the variable gadget enforces only one

of edges u i v i , u i vi to belongs G and that u i v i ∈ E(G) (resp. u i vi ∈ E(G))
if and only if the corresponding variable x i is true (resp. f alse), thus the appearance of such an edge in a clause gadget implies that there is a true literal in the clause.

Assume first that there is an (O 4 , H, 1)-graph G.

Claim 2. For each 1 ≤ i ≤ n, G contains either the edge u i v i or the edge

u i vi . Moreover, for each x ∈ {u i , v i , v i } there is some x ∈ V G i such that x and x are adjacent in G. Proof of claim: Since V G i contains J({u i , w i , w i }, B i ), by Claim 1, G contains
an edge e with both endvertices in {u i , w i , w i }. Assume that e is incident

to w i . Now V G i contains J({v i , w i , w i }, B i ). So, by Claim 1, G contains
an edge e with both endvertices in {v i , w i ,

w i }. Since ∆(G) ≤ 1, e is not incident to w i , so e = v i w i . Now V G i contains J({u i , v i , vi }, B i ). So, by
Claim 1, G contains an edge e with both endvertices in {u i , v i , vi }. This edge is not incident to v i , so e = u i vi . Similarly, we get that G contains vi wi and

u i v i if e is incident to w i .
In view of this claim, one defines the truth assignment φ by φ(

x i ) = true if u i v i ∈ E(G) and φ(x i ) = f alse if u i vi ∈ E(G). Let us prove that it satisfies Φ. Consider a clause C j = 1 ∨ 2 ∨ 3 and its corresponding clause gadget CG j . If there is none of u k j v k j in E(G) (for all k ∈ {1, 2, 3}
), that means both u k j and v k j are incident to an edge which is incident to a vertex in the variable gadget it they belongs to, T k j must be O 4 -overlaid by the edge s k j t k j .

So, t k j (for all k ∈ {1, 2, 3}) has degree one in G. However, the hyperedge

Z j is O 4 -overlaid by z j t k j or t k j t k j for k = k and k, k ∈ {1, 2, 3}, which implies that there is one of vertices t k j which is of degree one in G[Z j ]. It is a contradiction, thus there is an edge u k j v k j ∈ E(G) (for some k ∈ {1, 2, 3}).
Hence φ( k ) = true. Hence φ satisfies Φ.

Conversely, assume φ is a truth assignment satisfying Φ. Let G be the graph with vertex set V (H) and whose edge set is constructed as follows.

For every 1

≤ i ≤ n, add {u i v i , w i w i , u i w i , wi vi } to E(G) if φ(x i ) = true and {u i vi , wi w i , u i w i , w i v i } to E(G) if φ(x i ) = f alse. For every clause C j = 1 ∨ 2 ∨ 3 , there exists k ∈ {1, 2, 3} such that φ( k ) = true. Add the edges z j t k j , s k+1 j t k+1 j and s k+2 j t k+2 j (the superscript are modulo 3) to E(G). One easily checks that G is an (O 4 , H, 1)-graph. Theorem 4. (∆ ≤ 2)-O 3 -Overlay is N P-complete.
Proof. In order to simplify the proof, we will prove that the problem (∆ ≤ 2)-

O 3 -
V (H ) \ V (H)).
Conversely, (O 3 , H , 2)-graph G must contain the edge vt 1 v , and thus v is of

degree at most 1 in G [V (H)].
We reduce 3-SAT to (∆ ≤ 2)-O 3 -Overlay with handicap. Let Φ be an instance of 3-SAT with m clauses C 1 , . . ., C m on n variables x 1 , . . .,

x n . We construct a 3-uniform hypergraph H as follows (see Figure 4 for an example):

• for every variable x i , we create a variable gadget

V G i composed of vertices a 1 i , . . ., a p i i , α 1 i , . . ., α p i i , b 1 i , . . ., b p i i , β 1 i , . . ., β p i i , z 1 i , . . ., z p i i ,
and ζ 1 i , . . ., ζ p i i where p i is the number of clauses where x i appears.

Then, for every j ∈ [p i ], we create the following hyperedges (additions in superscripts are modulo p i , and we write p i instead of 0):

h 1 i,j = {z j i , a j i , α j i }, h 2 i,j = {z j i , b j i , β j i }, h 3 i,j = {a j i , z j i , b j i }, h 4 i,j = {z j i , b j i , ζ j i }, h 5 i,j = {b j i , ζ j i , a j+1 i }, h 6 i,j = {ζ j i , a j+1 i , z j+1 i }.
Moreover, all vertices z 1 i , . . ., z p i i , and ζ 1 i , . . ., ζ p i i are handicap vertices.

• for every clause C j , we create a clause gadget CG j composed of vertices c 1 j , . . ., c 5 j , and, for every p ∈ [5], of the hyperedge

{c p j , c p+1 j , c p+3 j } α 1 1 a 1 1 z 1 1 β 1 1 b 1 1 ζ 1 1 α 2 1 a 2 1 z 2 1 β 2 1 b 2 1 ζ 2 1 α 1 2 a 1 2 z 1 2 β 1 2 b 1 2 ζ 1 2 α 2 2 a 2 2 z 2 2 β 2 2 b 2 2 ζ 2 2 α 1 3 a 1 3 z 1 3 β 1 3 b 1 3 ζ 1 3 α 2 3 a 2 3 z 2 3 β 2 3 b 2 3 ζ 2 3 α 1 4 a 1 4 z 1 4 β 1 4 b 1 4 ζ 1 4 α 2 4 a 2 4 z 2 4 β 2 4 b 2 4 ζ 2 4 c 1 1 c 2 1 c 3 1 c 4 1 c 5 1 c 1 2 c 2 2 c 3 2 c 4 2 c 5 2 Figure 4: An example of the reduction for Φ = (x 1 ∨ x 2 ∨ x3 ) ∧ ( x2 ∨ x 3 ∨ x 4
). The dotted lines join two vertices that are identified. The thick red lines indicate the handicap vertices.

(additions are modulo 5, and we write 5 instead of 0). The vertices c 4 j and c 5 j are handicap vertices.

• finally, for every clause

C j = 1 ∨ 2 ∨ 3 , if p = x i ( p = xi ) for some p ∈ {1, 2, 3}
, then we identify the vertex c p j of CG j with the vertex

α j i (β j i ) of V G i , respectively.
The general idea of the proof is the following. There are only two possibilities to overlay a variable gadget V G i (either by a set T i or a set F i of edges).

See Claim 3. This two possibilities correspond to the two possible values (true or f alse) of the variable x i . Then a clause gagdet CG j imposes that not all literals of the clauses are assigned f alse with this correspondence.

Assume first that there is an (O 3 , H, 2)-graph G such that all handicap vertices have degree at most 1.

For i ∈ [n], let T i = p i j=1 {z j i a j i , b j i β j i , b j i ζ j i } and F i = p i j=1 {a j i α j i , z j i b j i , ζ j i a j+1 i }. Claim 3. Let i ∈ [n].
We have the following:

1. z j i ζ j i / ∈ E(G) and ζ j i z j+1 i / ∈ E(G), j ∈ [m]. 2. Either T i ⊆ E(G) or F i ⊆ E(G).
Proof of claim: 1. Assume for a contradiction that z j i ζ j i ∈ E(G). Since z j i and ζ j i are handicap vertices, the hyperedges h 2 i,j ,h 3 i,j , h 5 i,j must be O 3 -overlaid by the edges b j i β j i , a j i b j i , b j i a j+1 i , respectively, contradicting the fact that b j i has degree 2 in G.

Similarly, if ζ j i z j+1 i ∈ E(G), then the hyperedges h 5 i,j ,h 1 i,j+1 , h 3 i,j+1 must be O 3 - overlaid by the edges b j i a j+1 i , a j+1 i α j i , a j+1 i b j+1 i
, respectively, a contradiction.

2. By 1. the hyperedge h 4 i,j is O 3 -overlaid by z j i b j i or ζ j i b j i .

In the first case z j i b j i ∈ E(G), since z j i is a handicap vertex, the hyperedge h 6 i,j-1 must be O 3 -overlaid by ζ j-1 i a j i , and so hyperedge

h 3 i,j-1 is O 3 -overlaid by z j-1 i b j-1 i .
And by induction, we get that m j=1 {ζ j

i a j+1 i , z j i b j i } ⊆ E(G).
Since the z j i are handicap vertices, the hyperedge h 1 i,j is O 3 -overlaid by a j i α j i .

Hence

F i ⊆ E(G).
In the second case

ζ j i b j i ∈ E(G), a symmetrical argument shows T i ⊆ E(G).
We define the truth assignment φ by φ(

x i ) = true if T i ⊆ E(G) and φ(x i ) = f alse if F i ⊆ E(G)
. This is well-defined by Claim 3 and the fact that E(G) cannot contain both T i and F i because it has maximum degree 2. Now, for any j ∈ [m], there exists p ∈ {1, 2, 3} such that c p j has degree 2 in G[CG j ] (If not, then there are at most 2 edges. Hence there is a vertex c p j of degree 0, and thus there is a hyperedge containing c p j which is not overlaid). Therefore, it has degree 0 in the variable gadget c p j belongs to. By our definition of φ, we get that φ( p ) = true. Hence φ satisfies Φ.

Suppose now that φ : {x 1 , . . . , x n } → {true, f alse} is a truth assignment satisfying Φ.

Let us first select a set of edges in the variable gadgets. For every i ∈

[n], if φ(x i ) = true, then select edges {z j i , a j i }, {b j i , β j i } and {ζ j i , b j i } for all j ∈ [p i ].
If φ(x i ) = f alse, then select edges {z j i , b j i }, {a j i , α j i } and {ζ j i , a j+1 i } for all j ∈ [p i ] (additions are modulo p i ). Let E 1 be the set of selected edges, and

G 1 = (V (H), E 1 ).
Observe that G 1 O 3 -overlays the hyperedges of all variable gadgets: for every i ∈ [n] and every j ∈ [p i ],

• h 1 i,j contains the edge {z j i , a j i } if φ(x i ) = true, and the edge {a j i , α j i } otherwise.

• h 2 i,j contains the edge {b j i , β j i } if φ(x i ) = true, and the edge {z j i , b j i } otherwise.

• h 3 i,j contains the edge {z j i , a j i } if φ(x i ) = true, and the edge {z j i , b j i } otherwise.

• h 4 i,j contains the edge {ζ j i , b j i } if φ(x i ) = true, and the edge {z j i , b j i } otherwise.

• h 5 i,j contains the edge {ζ j i , b j i } if φ(x i ) = true, and the edge {ζ j i , a j+1 i } otherwise.

• h 6 i,j contains the edge {z j+1 i , a j+1 i } if φ(x i ) = true, and the edge {ζ j i , a j+1 i } otherwise.

Moreover the vertices z 1 i , . . ., z p i i , and ζ 1 i , . . ., ζ p i i have degree 1 in G 1 and the vertices α j i have degree 0 in G 1 if and only if φ(x i ) = true and the vertices

β j i have degree 0 in G 1 if and only if φ(x i ) = f alse.
We now select a set of edges in the clause gadgets for every clause Let k and p be two positive integers with p ≥ 2, let H k,p be the p-uniform hypergraph on (k+1)(p-1) vertices whose hyperedge set contains all possible p-subsets of vertices.

C j = 1 ∨ 2 ∨ 3 .
We first need the following claim in order to prove Lemma 1.

Claim 4. Every (O p , H k,p , k)-graph is k-regular. Moreover, there exists an

(O p , H k,p , k)-graph.
Proof of claim: Let G be an (O p , H k,p , k)-graph. Assume for a contradiction that it has a vertex v of degree at most k -1. Then, observe that

|V (G) \ N [v]| ≥ (k + 1)(p -2) + 1. Now,
(∆ ≤ k)-O p -Overlay to (∆ ≤ k + 1)-O p -Overlay.
Let H be a p-uniform hypergraph. Let H be the p-uniform hypergraph obtained from H by doing the following for each vertex v ∈ V (H):

• add the vertices x v , y v 1 , . . . , y v p-2 and the hyperedge S v = {v, x v , y v 1 , . . . , y v p-2 }.

• for any i = {1, . . . , p -2}, add a copy H v i of H k+1,p whose vertices are

y v i and (p -1)(k + 2) -1 new vertices.
Assume that G is an (O p , H , k+1)-graph. By Claim 4, the graph induced by Conversely, assume G is an (O p , H, k)-graph. Let G be the graph with vertex set V (H ) and whose edge set is the union of

G on V (H v i ) is (k + 1)-regular, for all v ∈ V (H), 1 ≤ i ≤ p -2.
E(G), {vx v | v ∈ V (H)},
and the edge set of an (O p , H i v , k + 1)-graph (which exists by Claim 4), for all

v ∈ V (H), 1 ≤ i ≤ p -2. One easily checks that G is (O p , H , k + 1)-graph.
Therefore, there is an (O p , H, k)-graph if and only if there is an

(O p , H , k + 1)-graph.
Propositions 1 and 2, Theorems 3 and 4, and Lemma 1 imply Theorem 1.

Complexity of Max (∆ ≤ k)-F -Overlay

The aim of this section is to establish Theorem 2 that gives the P/N Pcomplete dichotomy for the Max (∆ ≤ k)-F -Overlay problems.

As noticed in the introduction, if ∆(F ) > k or F is an anticomplete graph then Max (∆ ≤ k)-F-Overlay is trivially polynomial-time solvable.

Moreover, by Propositions 1 and 2, Max (∆ ≤ 1)-O 3 -Overlay as well as

Max (∆ ≤ k)-O 2 -Overlay (for all positive integers k) are also polynomialtime solvable.

We shall now prove that if we are not in one of the above cases, then

Max (∆ ≤ k)-F -Overlay is N P-complete. We first establish the N Pcompleteness when F has no isolated vertices.

Theorem 5. Let F be a graph on at least three vertices with no isolated

vertices. If k ≥ ∆(F ), then Max (∆ ≤ k)-F -Overlay is N P-complete on neat hypergraphs. Proof. Assume k ≥ ∆(F ). Let n = |F |, a 1 , . . . , a n be an ordering of the vertices of F such that δ(F ) = d(a 1 ) ≤ d(a 2 ) ≤ • • • ≤ d(a n ) = ∆(F ). Let γ = k/δ(F ) -1, β = k -γδ(F ). Observe that δ(F ) ≤ β ≤ 2δ(F ) -1.
We shall give a reduction from Independent Set which is a well-known N P-complete problem even for cubic graphs (see [? ].) We distinguish two cases depending on whether d(a 2 ) > β or not.

Let γ 2 = (k -d(a 2 ))/δ(F ) and γ 3 = (k -d(a 3 ))/δ(F ) . And we define the value γ 2 as follows.

-

If d(a 2 ) > β, let γ 1 = γ 2 . -If d(a 2 ) ≤ β, let γ 1 = (k -d(a 1 ))/δ(F ) .
Let Γ be a cubic graph. For each vertex v ∈ V (Γ), let (e 1 (v), e 2 (v), e 3 (v))

be an ordering of the edges incident to v. We shall construct the neat hypergraph H = H(Γ) as follows.

• For each vertex v ∈ Γ, we create a hyperedge

S v = {a v 1 , . . . , a v n }. Then,
for 1 ≤ i ≤ 3, we add γ i a v i -leaves, that are hyperedges containing a v i and n -1 new vertices.

• For each edge e = uv ∈ Γ, let i and j be the indices such that e = e i (u) = e j (v). We create a new vertex z e and hyperedges S e u (S e v )

containing z e , a u i (a v j ), and n -2 new vertices, respectively. Then, we add γ z e -leaves, that are hyperedges containing z e and n -1 new vertices.

From the construction, observe that γ i will be useful to enforce the degree of vertex a v i for v ∈ V (G) which could have degree at most d(a 3 ) in the hypergraph.

We shall prove that over

F (H, k) = (γ 1 +γ 2 +γ 3 )|V (Γ)| +(γ+1)|E(Γ)|+ α(Γ),
where α(Γ) denotes the cardinality of a maximum independent set in Γ.

The following claim shows that there are optimal solutions with specific structure. This leads to the inequality:

over F (H, k) ≤ (γ 1 + γ 2 + γ 3 )|V (Γ)| + (γ + 1)|E(Γ)| + α(Γ) Claim 5. There is a graph G with ∆(G) ≤ k that F -overlays over F (H, k)
hyperedges of H such that: Assume now that none of S e u , S e v is F -overlaid, and let e = e i (u), a u i has γ i

(a) each x-leaf L is F -overlaid and x is incident to δ(F ) edges in G[L] (with x = a v i or x = z e ).
a u i -leaves, so a u i is incident to γ i δ(F ) ≤ k -d(a i ) edges in these leaves.
Thus, replacing the edges of G in S e u by those of a copy of F , in which

-if d(a 2 ) > β, we have d G (a u i ) ≤ k -d(a 2 ),
then z e has degree δ(F ) and

a u i has degree d(a 2 ). -if d(a 2 ) ≤ β, since d G (a u 1 ) ≤ k -d(a 1
), then for i = 1, a u i must have degree d(a 1 ), so z e has degree d(a 2 ). And

for i = {2, 3}, let d(z e ) = d(a 1 ), d(a u i ) = d(a 2 ).
Hence, we obtain another graph with maximum degree at most k that Foverlays over F (H, k) hyperedges of H. Henceforth, we may assume that at least one of S e u and S e v is F -overlaid. This completes the proof of (b).

Consider now a vertex v ∈ V (Γ) such that S v is F -overlaid. We distinguish the following cases.

-If d(a 2 ) > β, then by (a), vertex

a v 1 is incident to γ 1 δ(F ) edges in the a v 1 - leaves and at least δ(F ) ∈ S v . Therefore S e 1 (v) v cannot be F -overlaid for otherwise, by (b), a v 1 would have degree at least γ 1 δ(F )+δ(F )+d(a 2 ) > k. Similarly, S e 2 (v) v cannot be F -overlaid.
Assume now for a contradiction that S

e 3 (v) v is F -overlaid. By (a) and (b), a v 3 is incident to γ 3 δ(F ) edges in the a v 3 -leaves and at least d(a 2 ) ∈ S e 3 (v) v . Since γ 3 δ(F ) + d(a 2 ) + d(a 3 ) > k, a v 3 is incident to less than d(a 3 ) edges in S v . Thus, there is a vertex a ∈ {a v 1 , a v 2 } which is incident to at least d(a 3 ) edges in S v and thus at least γ 1 δ(F ) + d(a 3 ) edges in G. But a v 3 is adjacent to at least δ(F ) edges in S v so at least γ 3 δ(F ) + d(a 2 ) + δ(F ) edges in total. Thus γ 3 δ(F ) + d(a 2 ) + δ(F ) ≤ k, so γ 3 ≤ γ 1 -1. Thus a is adjacent to at least (γ 3 + 1)δ(F ) + d(a 3 ) > k edges, a contradiction. -If d(a 2 ) ≤ β, then by (a), vertex a v 1 is incident to γ 1 δ(F ) edges in the a v 1 -leaves and at least δ(F ) ∈ S v . If S e 1 (v) v is F -overlaid, then (b) yields d(a v i ) = γ i δ(F ) + δ(F ) + δ(F ) > k, a contradiction. If S e 2 (v) v is F -overlaid, then d(a v 2 ) = δ in G[S v ]. We obtain that d(a v 2 ) = γ 2 δ + d(a 2 ) + δ ≤ k which implies that γ 2 ≤ γ 2 -1, a contradiction. If S e 3 (v) v
is F -overlaid, then we get a contradiction in the same way as that in the case d(a 2 ) > β.

To summarize, if

S v is F -overlaid, then none of S e 1 (v) v , S e 2 (v) v , S e 3 (v) v is F -overlaid.
Together with (b), this implies (c).

Conversely, consider W a maximum independent set of Γ.

Let G be the graph with vertex V (H) which is the union of the following subgraphs :

• for each x-leaf L, we add a copy of F on L in which x has degree δ(F );

• for each vertex v ∈ W , we add a copy of F on S v in which a v i has degree d(a i ) for all 1 ≤ i ≤ n.

• for each edge e ∈ E(Γ), we choose an endvertex u of e such that u / ∈ W , and add a copy of F in which z e has degree d(a 1 ) and a u i has degree d(a 2 ) (with i the index such that e i (u) = e) except the case when d(a 2 ) ≤ β and i = 1, we do that but d(z e ) = d(a 2 ) and d(a

u 1 ) = d(a 1 ) in G[S e 1 (u) u ].
It is simple matter to check that ∆(G) ≤ k and that G F -overlays

(γ 1 +γ 2 +γ 3 )|V (Γ)| +(γ+1)|E(Γ)|+α(Γ) hyperedges of H. Thus over F (H, k) ≥ (γ 1 + γ 2 + γ 3 )|V (Γ)| + (γ + 1)|E(Γ)| + α(Γ).
We then establish the following lemma, which allows to derive the N Pcompleteness of Max (∆ ≤ k)-F -Overlay when F has isolated vertices.

Lemma 2. Let k be a positive integer, let F be a graph with δ(F ) ≥ 1, and let q be a non-negative integer. If

Max (∆ ≤ k)-(F +K q )-Overlay is N P- complete, then Max (∆ ≤ k)-(F + K q+1 )-Overlay is also N P-complete.
must also (F + K q )-overlay S. Thus over

F +K q+1 (H, k) ≤ over F +Kq (H , k) + r |K| q+1 .
Now we can prove Theorem 2. As explained in the beginning of the section, it suffices to prove that Max (∆ ≤ k)-F -Overlay remains N P- Proof. Let H be a 4-uniform hypergraph.

complete when ∆(F ) ≤ k, F = K |F | , |F | ≥ 3 and (F, k) = (O 3 , 1). Assume
Let us describe an algorithm to decide whether there is a (C 4 , H, 3)-graph.

It is sufficient to do it when H is connected since the disjoint union of the (C 4 , K, 3)-graphs for connected components K of H is a (C 4 , H, 3)-graph.

Observe From now on we may assume that two hyperedges either do not intersect, or are adjacent (intersect on at least two vertices). Proof. Clearly, if H is not connected, it suffices to solve the problem on each of the components and to return 'No' if the answer is negative for at least one of the components, and 'Yes' otherwise. Henceforth, we shall now assume that H is connected. In such a case, a (P, H, 2)-graph is either a path or a cycle. However, if H is P-overlaid by a path P , then it is also P-overlaid by the cycle obtained from P by adding an edge between its two endvertices.

Thus, we focus on the case where G is a cycle.

Let S be a family of sets. The intersection graph of a family S is the graph IG(S) whose vertices are the sets of S, and in which two vertices are adjacent if the corresponding sets in S intersect.

The intersection graph of a hypergraph H, denoted by IG(H), is the intersection graph of its hyperedge set. We define two functions l H and s H as follows: l H (S) = |S|-1 for all S ∈ E(H) and s H (S, S ) = |S∩S |-1 for all S, S ∈ E(H).

Let C be the circle of circumference . We identify the points of C with the integer numbers (points) of the segment [0, ], (with 0 identified with ).

= (v 0 , v 1 , . . . , v n-1 , v 0 ).
There is a canonical embedding of C to C n in which every vertex v i is mapped to i and every edge v i v i+1 to the circular arc [i, i + 1]. For every hyperedge S ∈ E(H), P [S] is a subpath, which is mapped to the circular arc A S of C n that is the union of the circular arcs to which its edges are mapped. Clearly, Conversely, assume that IG(H) admits an (l H , s H )-respecting interval representation A = {A S | S ∈ E(H)} into C n . Let S 0 be a hyperedge of minimum size. Free to rotate all intervals, we may assume that

A = {A S | S ∈ E(H)} is an (l H , s H )-respecting interval representation of IG(H).
A S 0 is [1, |S 0 |]. Now since A is (l H , s H )-
respecting and H is connected, we deduce that the extremities of A S are integers for all S ∈ E(H). Let v 1 be a vertex of H that belongs to the hyperedges whose corresponding arcs of A contain 1. Then for all i = 2 to n = |V (H)|, denote by v i an arbitrary vertex not in {v 1 , . . . , v i-1 } that belongs to the hyperedges whose corresponding arcs of A contain i. Such a vertex exists because A is (l H , s H )-respecting. Observe that such a construction yields S = {v i | i ∈ A S } for all S ∈ E(H). Furthermore,

the cycle C = (v 1 , . . . , v n , v 1 ) P-overlays H. Indeed, for each S ∈ E(H), C[S] is the subpath corresponding to A S , that is V (C[S]) = {v i | i ∈ A S } and E(C[S]) = {v i v i+1 | [i, i + 1] ⊆ A S }.
The algorithm to solve (∆ ≤ 2)-P-Overlay for a connected hypergraph H in linear time is thus the following:

1. Construct the intersection graph IG(H) and compute the associated functions l H and s H .

2. Check whether graph IG(H) has an (l H , s H )-respecting interval representation. If it is the case, return 'Yes'. If not return 'No'.

Remark 1. We can also detect in polynomial time whether a connected hypergraph H is P-overlaid by a path. Indeed, similarly to Claim 9, one can show that there is a path P-overlaying H if and only if IG(H) admits an (l H , s H )-respecting interval representation.

On neat hypergraphs

Let F = (V, E) be a graph. We denote by V i the set of vertices having degree i in F . For every increasing sequence of nonnegative integers i 1 < i 2 < • • • < i p , an (i 1 , i 2 , . . . , i p )-graph is a graph F such that V i = ∅ if i / ∈ {i 1 , i 2 , . . . , i p }. In particular, an (r)-graph is a r-regular graph.

Given a hypergraph H, we denote by d H (v) the number of hyperedges containing v for any v ∈ V (H).

Theorem 8. Let i 1 , i 2 , k be three non-negative integers with i 1 < i 2 . For every (i 1 , i 2 )-graph F , one can solve (∆ ≤ k)-F -Overlay in polynomial time on neat hypergraphs.

Proof. Let H be a neat |F |-uniform hypergraph.

If there is a vertex v such that i 1 •d H (v) > k, then we answer 'No'. Indeed in an (H, F, k)-graph G, the vertex v has degree at least i 1 in each subgraph of G induced by a hyperedge to which it belongs, and so degree at least

i 1 • d H (v) in G
(v) = i 2 •d B (v)+i 1 (d H (v)-d B (v)) = i 1 •d H (v)+(i 2 -i 1 )d B (v).
But G is an (H, F, k)-graph, so d G (v) ≤ k. With the previous equality, this

yields d B (v) ≤ k-i 1 •d H (v) i 2 -i 1 , and so d B (v) ≤ k-i 1 •d H (v) i 2 -i 1 .
Problem 1. Characterize the pairs (F, k) for which Max (∆ ≤ k)-F-Overlay is polynomial-time solvable and those for which it is N P-complete.

Theorem 1 and the results obtained in Section 4 give a first view of the complexity of (∆ ≤ k)-F -Overlay. A natural problem is to close the dichotomy:

Problem 2. Characterize the pairs (F, k) for which (∆ ≤ k)-F -Overlay is polynomial-time solvable and those for which it is N P-complete.

It would be interesting to consider the complexity of this problem when F is k-regular but non-connected, and when F is a cycle. In order to attack Problem 2, it would be helpful to prove the following conjecture. As shown in Subsection 4.3, we proved that (∆ ≤ k)-F -Overlay is sometimes easier when restricted to neat hypergraphs. It would then be interesting to determine the complexity of (∆ ≤ k)-F -Overlay on neat hypergraphs.

So far, we only proved some of these problems to be polynomial-time solvable, but we believe some are N P-complete.

Problem 3. Characterize the pairs (F, k) for which (∆ ≤ k)-F -Overlay on neat hypergraphs is polynomial-time solvable and those for which it is N P-complete.

  Figure 1: A hypergraph composed of seven vertices and four hyperedges (right). A graph G satisfying local properties (every hyperdge induces a connected subgraph in G) and a global property (the total number of edges is at most the number of vertices).

H

  and an integer m, decide if there exists a graph G F-overlaying H such that |E(G)| ≤ m. A typical example of a family F is the set of all connected graphs, in which case M(F) is the set of all trees. Agarwal et al. [? ] focused on min-M(F)-Overlay for this particular family in the aforementioned context of structural biology. However, this problem was previously studied by several communities in other domains, as pointed out by Chen et al.[? ]. Indeed, it is also known as Subset Interconnection Design, Minimum Topic-Connected Overlay or Interconnection Graph Problem, and was considered (among others) in the design of vacuum systems [? ? ], scalable overlay networks [? ? ], and reconfigurable interconnection networks [? ? ]. Some variants have also been considered in the contexts of inferring a most likely social network [? ], determining winners of combinatorial auctions [? ], as well as drawing hypergraphs [? ? ]. Cohen et al. [? ] presented a dichotomy regarding the polynomial vs.N P-hard status of the problem min-F-Overlay with respect to the considered family F. Roughly speaking, they showed that the easy cases one can think of (e.g. when edgeless graphs of the right sizes are in F, or if F contains only cliques) are the only families giving rise to a polynomial-time solvable problem: all others are N P-complete. They also considered the FPT/W[1]-hard dichotomy for several families F.

Figure 2 :

 2 Figure 2: Example of (∆ ≤ k)-F-overlay and max (∆ ≤ k)-F-overlay. In the figure, an instance H (left), a graph G with ∆(G) ≤ 1 that O 3 -overlays H (with O 3 being the graph with three vertices and one edge) (center), and a solution to Max (∆ ≤ 3)-C 3overlay (with C 3 being the cycle on three vertices) (right).

  respectively. By definition those two problems really make sense only for |F |-uniform hypergraphs i.e. hypergraphs whose hyperedges are of size |F |. Therefore, we always assume the hypergraph to be |F |-uniform. If F is a graph with maximum degree greater than k, then solving (∆ ≤ k)-F -Overlay or Max (∆ ≤ k)-F -Overlay is trivial as the answer is always 'No'. So we only study the problems when ∆(F ) ≤ k. If F is an anticomplete graph (i.e. with no edges), then Max (∆ ≤ k)-F -Overlay is also trivial, because for any hypergraph H, the anticomplete graph on V (H) vertices F -overlays H. Hence the first natural interesting cases are the graphs with one edge. For every integer p ≥ 2, we denote by O p the graph with p vertices and one edge. In Section 2, we prove the following dichotomy theorem. Theorem 1. Let k ≥ 1 and p ≥ 2 be integers. If p = 2 or if k = 1 and p = 3, then Max (∆ ≤ k)-O p -Overlay and (∆ ≤ k)-O p -Overlay are polynomial-time solvable. Otherwise, they are N P-complete.

  [p] = {1, . . . , p}. In some proofs of the paper we might use the modulo operation to keep indices in bounds. Given S ⊆ V (G), we denote by G[S] the subgraph induced by S, that is the subgraph with vertex set S and edge set {uv ∈ E(G) | u, v ∈ S}. We denote by K k the anticomplete graph on k vertices, that is the graph with k vertices and no edges. The disjoint union of two graphs F and G is denoted by F + G.

  J) = A ∪ B with |A| = 3 and |B| = 4 and E(J) = {A ∪ {b} | b ∈ B}. Claim 1. Every (O 4 , J, 1)-graph contains exactly one edge with both endvertices in A.Proof of claim: Let G be an (O 4 , J, 1)-graph. Each hyperedge of J contains an edge of G, which necessarily has an endvertex in A. Since ∆(G) ≤ 1, G has at most three edges with an endvertex in A. Since J has four hyperedges, there is an edge of G contained in two hyperedges of J. The two endvertices of this edge are in A.

E 2

 2 Since φ satisfies Φ, there exists p = p j ∈ {1, 2, 3} such that φ( p ) = true. Select the edges {c p j be the set of selected edges in clause gadgets, andG 2 = (V (H), E 2 ).Clearly, G 2 O 3 -overlays all hyperedges of the clause gadgets and the vertices c 4 j and c 5 j , j ∈ [m], have degree 1 in G 2 . Moreover, for all j ∈ [m] the vertex c p j j is identified with the vertex α j i or β j i , which has degree 0 in G 1 sinceφ( p ) = true. Thus G := (V (H), E 1 ∪ E 2 ) has maximum degree 2, whichproves that it is an (O 3 , H, 2)-graph.Lemma 1. If (∆ ≤ k)-O p -Overlay is N P-complete, then (∆ ≤ k)-O p+1 -Overlay and (∆ ≤ k + 1)-O p -Overlay are N P-complete.

  Therefore each y v i has k+1-neighbours outside the hyperedge S v . Hence G must contain the edge vx v because it O p -overlays S v . Thus the subgraph G = G [V (H)] has maximum degree at most ∆(G ) -1 ≤ k and G O p -overlays H. In other words, G is an (O p , H, k)-graph.

  (b) for each edge e = uv ∈ E(Γ), exactly one of the two hyperedges S e u and S e v is F -overlaid. Moreover if S e u (S e v ) is F -overlaid, then a u i (a v j ) is incident to at most d(a 2 ) edges in S e u (S e v ), respectively.(c) the set of vertices v such that S v is F -overlaid is an independent set in Γ.Proof of claim:Let G be a graph with ∆(G) ≤ k that F -overlays over F (H, k)hyperedges of H. Observe first that since H is a neat hypergraph, we may assume that, for every hyperedgeS of H, G[S] = F if S is F -overlaid and G[S] has no edge otherwise. Therefore if an x-leaf L is F -overlaid, then replacing G[L] by a copy of Fin which x has degree δ(F ), we obtain another graph with maximum degree at most k that F -overlays over F (H, k) hyperedges of H. Henceforth we may assume that if an x-leaf is F -overlaid then x is incident to δ(F ) edges included in it.Now assume that the z e -leaf L, for e ∈ E(Γ), is not F -overlaid by G. We have d G (z e ) > k -δ(F ) for otherwise adding on L the edges of a copy of F in which z e has degree δ(F ), we obtain a graph F -overlaying more hyperedges than G. But since there are γ z e -leaves and z e is incident to δ(F ) edges in each of them, at least one of the hyperedges S e u and S e v is F -overlaid. Now replacing the edges of G in this hyperedge by those of a copy of F in L, in which z e has degree δ(F ), we obtain another graph with maximum degree at most k that F -overlays over F (H, k) hyperedges of H. Henceforth we may assume that every z e -leaf is F -overlaid.A similar reasoning shows that every a v i -leaf is F -overlaid, for all v ∈ V (Γ), i ∈ {1, 2, 3}. This proves (a).Now by (a) each vertex z e is incident to γδ(F ) = k -β > k -2δ(F )edges in the z e -leaves. Thus z e is incident to at most β edges in S e u ∪ S e v . Since β ≤ 2δ(F ) -1, at most one of S e u and S e v is F -overlaid. Moreover, if S e u is F -overlaid and β < d(a 2 ) (resp. d(a 2 ) ≤ β), then z e must have degree d(a 1 ) (resp. at most d(a 2 )) in G[S e u ].

  that the above conditions are satisfied. Let F be the graph induced by the non-isolated vertices of F . Then F = F +K q with q = |F |-|F |. If |F | = 2, then F = O |F | , and we have the result by Theorem 1. If |F | ≥ 3, then the result follows from Theorem 5, Lemma 2, and an immediate induction.4. Complexity of (∆ ≤ k)-F -Overlay and (∆ ≤ k)-F -OverlayIn this section, we investigate the complexity of (∆ ≤ k)-F -Overlay and (∆ ≤ k)-F-Overlay problems. We believe that each such problem is either polynomial-time solvable or N P-complete. However the dichotomy is more complicated than the one we proved in Theorem 2 for Max (∆ ≤ k)-F -Overlay. This dichotomy is simple because there are very few pairs (F, H) for which Max (∆ ≤ k)-F -Overlay is polynomial-time solvable. We now exhibit several pairs (F, k) such that (∆ ≤ k)-F -Overlay is polynomialtime solvable, while Max (∆ ≤ k)-F -Overlay is N P-complete.4.1. Regular graphsProposition 3. For every complete graph K and every positive integer k,(∆ ≤ k)-K-Overlay is polynomial-time solvable. Proof. Observe that a |V (K)|-uniform hypergraph H is a positive instance of (∆ ≤ k)-K-Overlay if and only if K(H) is a (K, H, k)-graph.Proposition 4. For every connected k-regular graph F , (∆ ≤ k)-F -Overlay is polynomial-time solvable. Proof. One easily sees that a |V (F )|-uniform hypergraph H admits an (F, H, k)graph if and only if the hyperedges of H are pairwise non-intersecting. Let C 4 denote the cycle on 4 vertices. Proposition 4 implies that (∆ ≤ 2)-C 4 -Overlay is polynomial-time solvable. We now show that (∆ ≤ 3)-C 4 -Overlay is also polynomial-time solvable. Theorem 6. (∆ ≤ 3)-C 4 -Overlay is polynomial-time solvable.

Claim 7 .

 7 If two hyperedges S 1 and S 2 intersect on three vertices and there is a (C 4 , H, 3)-graph G, then |V (H)| ≤ 6. Proof of claim: Assume S 1 = {a 1 , b, c, d} and S 2 = {a 2 , b, c, d}. Let G be a (C 4 , H, 3)-graph. Observe that a 1 and a 2 must have two common neighbours, say b, c, in common in {b, c, d}, for otherwise their unique common vertex would have degree 4 in G. This forces d to be also adjacent to b and c. Consider a hyperedge S 3 intersecting S 1 ∪S 2 . Since it is C 4 -overlaid by G, at least two edges connect S 3 ∩ (S 1 ∪ S 2 ) to S 3 \ (S 1 ∪ S 2 ). The endvertices of those edges in S 1 ∪S 2 must have degree 2 in G[S 1 ∪S 2 ]. Hence, without loss of generality, there is a vertex e not in S 1 ∪S 2 such that either S 3 = {a 1 , a 2 , b, e} and {a 1 e, a 1 e} ⊆ E(G), or S 3 = {a 1 , b, d, e} and {a 1 e, de} ⊆ E(G). Now no hyperedge can both intersect S 1 ∪ S 2 ∪ S 3 and contain a vertex not in S 1 ∪ S 2 ∪ S 3 , for such a hyperedge must contain either the vertices d, e or a 2 , e which are at distance 3 in G[S 1 ∪ S 2 ∪ S 3 ]. (However there can be more hyperedges contained in S 1 ∪ S 2 ∪ S 3 .) Hence |V (H)| ≤ 6. In view of Claim 7, if there are two hyperedges with three vertices in common, either we return 'No' if |V (H)| > 6, or we check all possibilities (or follow the proof of the above claim) to return the correct answer otherwise. Henceforth, we may assume that any two adjacent hyperedges intersect in exactly two vertices. Let S 1 and S 2 be two adjacent hyperedges, say S 1 = {a, b, c, d} and S 2 = {c, d, e, f }. Note that every (C 4 , H, 3)-graph contains the edges ab, cd and ef , and that N (c) ∪ N (d) = S 1 ∪ S 2 in this (C 4 , H, 3)-graph. Claim 8. If there is another hyperedge than S 1 and S 2 containing c or d, and there is a (C 4 , H, 3)-graph G, then |V (H)| ≤ 8.

A

  circular-arc graph is the intersection graph of a set of arcs on C . A set A of arcs such that IG(A) = G is called an arc representation of G. We denote by A v the arc corresponding to v in A. Let G be a graph and let l : V (G) → N and s : E(G) → N be two functions. An arc representation A of G is l-respecting if A v has length l(v) for any v ∈ V (G), s-respecting if A v ∩ A u has length s(u, v) for all uv ∈ E(G), and (l, s)-respecting if it is both l-respecting and s-respecting. One can easily adapt the algorithm given by Köbler et al. [? ] for (l, s)-respecting interval representations to decide in linear time whether a graph admits an (l, s)-respecting arc representation in C n for every integer n. Claim 9. Let H be a connected hypergraph on n vertices. There is a cycle P-overlaying H if and only if IG(H) admits an (l H , s H )-respecting arc representation into C n . Proof of claim: Assume that H is P-overlaid by a cycle C

Figure 5 :

 5 Figure5: Given a hypergraph H (left), we determine its graph IG(H) (middle) with each vertex represents the a hyperedge of the same color in which the value of any vertex S ∈ V (H) is l H (S) and the weight of an edge between S, S is s H (S, S ). And a circular arc representation (each arc is associated to a hyperedge of the same color) is shown in the right which is (l, s)-respecting.

  because H is neat. Hence, we assume that i 1 • d H (v) ≤ k for every vertex.Let B(H) be the incidence graph of H: its vertex set is E(H) ∪ V (H) and there is an edge between a hyperedge S ∈ E(H) and a vertex v ∈ V (H) if and only if v ∈ S.Claim 10. There is an (H, F, k)-graph if and only if B(H) has a subgraph in which every hyperedge vertex has degree |V i 2 | and every vertex has degreeat most k-i 1 •d H (v) i 2 -i 1 .Proof of claim: Assume that there is an (H, F, k)-graph G. Observe that since H is a neat hypergraph, free to remove some edges, we may assume that G[S] is isomorphic to F for every hyperedge S of H. Let B be the subgraph of B(H) in which a vertex v is adjacent to a hyperedge S if and only if v has degree i 2 in G[S]. By definition every hyperedge has degree |V i 2 | in B . Consider now a vertex v. Its degree in G is the sum of its degree in the subgraphs induced by the hyperedges S to which it belongs because H is neat. Hence d G

Conjecture 1 .

 1 If (∆ ≤ k)-F -Overlay is N P-complete, then (∆ ≤ k +1)-F -Overlay is also N P-complete. Furthermore, for each pair (F, k) such that Max (∆ ≤ k)-F-Overlay is N P-complete and (∆ ≤ k)-F-Overlay is polynomial-time solvable, it is natural to consider the parameterized complexity of Max (∆ ≤ k)-F-Overlay when parameterized by |E(H)| -s, because (∆ ≤ k)-F-Overlay is the case s = 0.It would also be interesting to obtain approximation algorithms for Max (∆ ≤ k)-F-Overlay when this problem is N P-complete.

  {x, y} ⊆ S}. The edge-weight function induced by H on K(H), denoted by w H , is defined by w H (e) = |{S ∈ E(H) | e ⊆ S}|. In words, w H (e) is the number of hyperedges of H containing e. A hypergraph H is connected if K(H) is connected, and

	the connected components of a hypergraph H are the connected components
	of K(H). Finally, a graph G F -overlaying H with maximum degree at most
	k is called an (F, H, k)-graph (resp. (F, H, k)-graph) for F is a graph (resp.
	graph family).

  Finally, observe that the disjoint union of p -1 cliques of size k + 1 is a k-regular graph which O p -overlays H k,p . from a copy of H and replace, for every hyperedge S, a hyperedge S = S ∪ {v s }. We also add, for every hyperedge S, a set of (k + 1)p -1 new vertices N S , and form, together with v S , a hypergraphH S isomorphic to H k,p+1 .Let G be an (O p , H, k)-graph. Construct G

	by removing successively the closed neighbourhood of a vertex of the graph (chosen arbitrarily) until the graph is anticomplete, we can construct, together with v, an independent set S of G of size p. This is impossible, since S is a hyperedge of H k,p which is not (∆ ≤ k)-O p+1 -Overlay. Let H be a p-uniform hypergraph. We construct O Proof of Lemma 1. First, we will reduce from (∆ ≤ k)-O p -Overlay to a (p + 1)-uniform hypergraph H

p -overlaid by G. * * from G by adding, for every hyperedge S of H, a disjoint union of p cliques of size k + 1 on the vertices

N S ∪ {v S }. Clearly, G * is an (O p+1 , H * , k)-graph.

Conversely, if G * is an (O p+1 , H * , k)-graph, then, by Claim 4, v S must have degree k in N S for every hyperedge S of H. Thus, the restriction of G * to the vertices of H is an (O p , H, k)-graph.

Now, we reduce

  first that if two hyperedges of H intersect in exactly one vertex u, then no such graph exists, since u must have degree 2 in each of the hyperedges if they are C 4 -overlaid, and thus degree 4 in total. Therefore if there are two such hyperedges, we return 'No'. At this point we may assume that |E(H)| ≥ 2 for otherwise we return 'Yes'.

Proof. We shall reduce Max (∆ ≤ k)-(F + K q )-Overlay to Max (∆ ≤ k)-(F + K q+1 )-Overlay. Set p = |V (F )| and r = k/δ(F ) . Note that r ≥ 1, for otherwise Max (∆ ≤ k)-(F + K q )-Overlay would trivially be polynomial-time solvable.

Let H be a (p + q)-uniform hypergraph. Let H be the (p + q + 1)-uniform hypergraph obtained from H as follows. Its vertex set is partitioned into V (H ), P 1 , . . . , P r , K, and {z} with |P i | = p -1 for all 1 ≤ i ≤ r and |K| = (m + 1)(k + 1) + kp with m = max{|E(H )|, q + 1}. The hyperedge set of H contains Q ∪ P i ∪ {z} for all (q + 1)-subsets Q of K and all 1 ≤ i ≤ r, and S ∪ {z} for all S ∈ E(H ).

The reduction can be performed in polynomial time, because for each hyperedge in H we construct a polynomial number of hyperedges in H (recall that q is fixed), and each of them is straightforward to obtain. We shall now prove that over Conversely, let G be a graph with V (G) = V (H) and ∆(G) ≤ k that maximizes the number of (F + K q+1 )-overlaid hyperedges.

Claim 6. In G, vertex z has at least δ(F ) neighbours in each P i , 1 ≤ i ≤ r.

Proof of claim: Suppose for a contradiction that z has less than δ(F ) neighbours in P i . Since ∆(G) ≤ k, at most kp vertices of K are incident to an edge with an endvertex in P i ∪{z}. Thus there is a subset R of K of (m+1)(k +1) vertices non-adjacent to all vertices of

vertices of degree less than δ(F ) (namely the ones of Q ∪ {z}), and so the hyperedge If H contains both S 3 and S 4 , then G contains the edges ag, eg, bh Clearly, the above-described algorithm runs in polynomial time.

Paths

Let P be the set of all paths. We have the following:

Theorem 7. (∆ ≤ 2)-P-Overlay is linear-time solvable.

Conversely, assume B(H) has a subgraph B in which every S ∈ E(H)

. We construct G as follows: for each hyperedge S, the induced subgraph

is a copy of F such that any vertex v where (S, v) ∈ E(B ) is of degree i 2 (there are |V i 2 | such vertices) and the remaining vertices have degree i 1 .

Clearly, G F -overlays H. Moreover every vertex v ∈ V (H) has degree i 2 Theorem 9. Let i 1 , i 2 , i 3 , k be three non-negative integers with

Overlay in polynomial time on neat hypergraphs.

Proof. Let j be the number of neighbours in

Let H be an |F |-uniform hypergraph. Observe that if a vertex has degree for every v ∈ V (H ). Since all vertices of V i 1 ∪ V i 2 have exactly j neighbours in V i 3 , it is then easy to prove the following claim:

Claim 11. There is an (H, F, k)-graph G if and only if there is a graph G F -overlaying H such that d G (v) ≤ k (v) for all v ∈ V (H ).

Deciding whether such a graph G exists can be done similarly as the proof of Theorem 8 replacing k by k (v).

Further research

Theorem 2 characterizes the complexity of Max (∆ ≤ k)-F-Overlay when F contains a unique graph. It would be nice to extend this characterization to families F of arbitrary size.


Yousef Taheri
email: yousef.taheri@lip6.fr

Gauvain Bourgne
email: gauvain.bourgne@lip6.fr

Jean-Gabriel Ganascia
email: jean-gabriel.ganascia@lip6.fr

A Compliance Mechanism for Planning in Privacy Domain Using Policies

Keywords: Automatic Compliance Checking, AI planification, Compliance Mechanism, Personal Data Privacy

As more and more applications relying on the use and processing of personal data grow, privacy protection is becoming increasingly important. With the enforcement of the GDPR, such applications must guarantee compliance with the obligations set forth. Integrating a compliance checking mechanism with AI methods is helpful to fulfill this requirement. Toward this end, we investigate the GDPR automatic compliance checking using a planning system including personal data and an agent with actions that process data. We propose a modular framework that is capable to generate possible plans (sequence of data processing) to satisfy a given goal state, check the compliance of the plan with GDPR regulatory constraints, and provide explanation of missing obligations in case of a non-compliant. We use Answer Set Programming(ASP) and event calculus formalism to model the planning problem and make use of SPECIAL policy language as an existing work to translate GDPR requirements into ASP.

Introduction

AI applications handling personal data is being largely adopted by many companies and data processors to deliver their services to their users. Building trustworthy AI and enhancing liability in society requires tools and techniques to ensure users privacy protection. The European General Data Protection Regulation (GDPR) provides legal requirements concerning personal data processing. Organizations need to take technical measures to evaluate the compliance of personal data processing with GDPR. Compliance mechanism tools help these organizations to fulfill their need for compliance assessment.

Many of the AI products require handling personal data through an automated procedure, therefore, they need to be integrated with compliance mechanisms to operate lawfully. Most of the current works on compliance checking focus on either representing GDPR concepts as Palmirani et al. [START_REF] Palmirani | Legal ontology for modelling gdpr concepts and norms[END_REF] or building policy pipeline for representing regulatory norms and business policies De Vos et al. [START_REF] Vos | Odrl policy modelling and compliance checking[END_REF], Bonatti et al. [START_REF] Bonatti | Machine understandable policies and gdpr compliance checking[END_REF]. These tools are built for assessing the compliance of a business policy, which is used to represent characteristics of a data processing.

However, none of them has studied the integration of GDPR compliance checking in planning or an automatic data manipulation setting. Bandara et al. [START_REF] Bandara | Using event calculus to formalise policy specification and analysis[END_REF] introduces a policy specification and enforcement method in a dynamic environment. They use it for detecting conflicts among policies and do not concern with personal data and privacy protection. De Vos et al. [START_REF] Vos | Legal modelling and reasoning using institutions[END_REF] propose a methodology to support legal reasoning using institutions (systems that specify normative behavior of participants) and a corresponding computational model. Given a set of observed actions their method captures the evolution of legal model after each action in a multi-agent setting, but it does not include automatic action generation and also does not deal with privacy domain.

In this paper, we build an agent that is capable to generate a sequence of personal data manipulations that are compliant with GDPR legal constraints. The agent can change the state of the system by performing a data processing e.g. transfer, analyze, etc. Each state in the planning domain represents a characteristic of the personal data. The agent is capable to reach a given a target state, by performing a number of processes on personal data called a plan. We are interested in the plan's compliance with GDPR regulatory norms, including the data subject's given consent. Toward this end, we propose a modular framework with the following components.

-Planning, Given a goal state, an initial state and a description of the domain, this module generates all possible plans regardless of their compliance. -Compliance Engine, Given a plan, this module checks for its compliance against GDPR regulatory norms, and data subject's given consent. In the case of a non-compliant plan, it explains the missing obligations.

In order to do planning while checking for compliance we need a logical formalism that deals with sequence of actions while keeping track of the world state at each step of execution. Furthermore, since expressivity is essential in the current (and future) work, such formalism should enable modeling complex narratives with multiple events. A useful candidate, is event calculus (cf. Shanahan [START_REF] Shanahan | The event calculus explained[END_REF]), a well-known formalism in the planning literature. Event calculus uses an explicit linear representation of time in which fluents hold and events occur. In other words, the linear time-line is used to associate states and events when a change happens in the world. Combined with non-monotonic reasoning, event calculus allows exploring different alternatives as required for planning. Therefore, it eliminates the need for a more expressive or complex formalism based on branching-time, such as situation calculus. We give a more precise description at Section 2.2.

We also need to represent GDPR regulatory norms, in order to support compliance checking. To do so, we chose to use the SPECIAL policy language which offers a unified representation of regulatory norms and data subject's given consent to enable compliance checking of business policies.

In a legal setting we deal with a potentially large body of knowledge in the related law and there are usually multiple constraints which need to be verified to assess compliance. In order to implement such a domain we need a formalism that allows on one hand to express both rules and facts, and on the other hand it has to support non-monotonic reasoning (since we would normally encounter situations with incomplete information). Answer Set Programming (ASP) (cf. Lifschitz [START_REF] Lifschitz | Answer set programming[END_REF]) is a proper candidate for this purpose. A knowledge representation and reasoning paradigm with an expressive formalism and efficient solvers. ASP is largely used for common sense reasoning, abductive and deductive reasoning and is especially suitable for planning and dealing with incomplete knowledge. ASP is compatible with event calculus and is a practical choice for future developments of our current work. We use Clingo by Gebser et al. [START_REF] Gebser | Clingo= asp+ control: Preliminary report[END_REF], as an answer set solver for ASP. Briefly speaking, it is composed of two main steps; (i)The grounder which takes as input the provided knowledge, substitute all variables with the given instances, (ii)The solver which takes the extended knowledge of the previous step as input and extract the answer sets which are basically stable models of the program.

The rest of the paper is organized as follows: Section 2 presents both a brief background on SPECIAL policy language and the version of event calculus used to model the planning domain. In Section 3 we explain our modular framework and describe how each component is constructed. In Section 4 we evaluate our framework on two simple scenarios, and discuss the results. Section 5 presents a brief discussion of the related works. Finally, in Section 6 we discuss the conclusions and mention the future works.

Backgrounds

The SPECIAL Policy Language

In order to support automated compliance checking, we need a representation of GDPR requirements in a machine understandable format. Such representation is required to construct the compliance engine in our modular framework (see Figure 1). There are many works trying to develop an ontology or a policy pipeline to represent GDPR requirements for compliance checking. Here we make use of the SPECIAL, a policy language based on OWL2, that offers a unified representation for consent, business policies, and regulatory obligations.

In the SPECIAL policy language, a personal data processing is formalized as a business policy. The following is an example of a business policy, each attribute describes a characteristic of the personal data handling. ) ) ObjectSomeValuesFrom ( s b p l : h a s D u t y g e t V a l i d C o n s e n t ) ObjectSomeValuesFrom ( s b p l : h a s D u t y g e t A c c e s s R e q s ) ObjectSomeValuesFrom ( s b p l : h a s D u t y g e t R e c t i f y R e q s ) ObjectSomeValuesFrom ( s b p l : h a s D u t y g e t D e l e t e R e q s ) ObjectSomeValuesFrom ( s b p l : h a s L e g a l B a s i s A6-1-a-c o n s e n t ) )

Listing 1.1: a business policy in SPECIAL The above attributes for this business policy are described respectively as follows, (i) The category of the personal data used in the processing is Purchases and Spending Habit, (ii) the processing category is analyze, (iii) The purpose of the processing is Marketing, (iv) the recipient of the processing result is aCompany, (v) the processing is taking place in a storage located in Europe and the duration of data storage is Indefinite, (vi) the duties defined for this processing, for example getValidConsent means that the specified software can read the data sources if consent has been given, (vii) the legal basis the processing is A6-1-aconsent. The values of these attributes are selected from a suitable vocabulary. SPECIAL uses the W3C's Data Privacy Vocabularies and Controls Community Group, (DPVCG) Pandit et al. [START_REF] Pandit | Creating a vocabulary for data privacy[END_REF]. We have made use of the same vocabulary for the terms in our framework, which will be presented in Section 3

Consent Representation A consent is represented as a usage policy in SPE-CIAL and expresses the characteristics of the processing for which the data subject has given his consent. Consent has the same attributes as business policy but, without legal basis and duties. For example, the following policy demonstrates data subject's consent to transfer his Service Consumption Behavior data with the purpose Create Personalized Recommendations. The recipient is aCompany, the storage is located in Europe, and it is valid for a duration of 365 days. DataSomeValueFrom ( h a s d u r a t i o n D a t a t y p e R e s t r i c t i o n ( x s d : i n t e g e r x s d : m i n I n c l u s i v e " 3 6 5 " x s d : i n t e g e r ) ) ) )

Listing 1.2: A consent in SPECIAL

A business policy is compliant with data subject's consent, if the business process is a subclass of the given consent.

Regulatory Norms In the SPECIAL policy language, the GDPR regulative norms in the form of permissions, obligations, and prohibitions are formalized as the constraints that should hold over the different attributes of a business policy. As an example Article 6-1 (lawfulness) the class Art6_1 is formalized as follows, it means that a business process holds the obligation of this article if it has a legal basis from the provided list in Article 6-1.

ObjectSomeValuesFrom ( h a s L e g a l B a s i s O b j e c t U n i o n O f ( A r t 6 1 a C o n s e n t A r t 6 1 b C o n t r a c t A r t 6 1 c L e g a l O b l i g a t i o n A r t 6 1 d V i t
a l I n t e r e s t A r t 6 1 e P u b l i c I n t e r e s t A r t 6 1 f L e g i t i m a t e I n t e r e s t ) )

Obligations are formalized as classes and can be combined by operations ObjectUnionOf or ObjectIntersectOf to form the GDPR obligations at the top level partially. For example, the obligations of Chapter 2 of GDPR (Principles) is modeled is SPECIAL as a union of the obligations of Article 6 (Lawful processing), Article 9 (Sensitive Data), and Article 10 (Criminal Data).

O b j e c t U n i o n O f (

A r t 6 L a w f u l P r o c e s s i n g A r t 9 S e n s i t i v e D a t a A r t 1 0 C r i m i n a l D a t a )

The above expression means the processing is lawful if either the obligations of Article 6 (Lawful Processing), or Article 9 (Sensitive Data), or Article 10 (Criminal Data), are satisfied.

Event Calculus

Event Calculus (EC) is a logic based formal language for representing events and their effects. It has first been introduced by Kowalski and Sergot [START_REF] Kowalski | A logic-based calculus of events[END_REF]. Various versions of the Event Calculus has been used in the literature. In this work, we use a specific version taken from Berreby et al. [START_REF] Berreby | A declarative modular framework for representing and applying ethical principles[END_REF]. It relies on formal representation of events and states on a discrete set of time points. The dynamic state of the world is represented by a set of properties called fluent that hold or not at any time point. Transition between the states is made by events that occur in time T . These events are characterized by preconditions that must hold for the event to occur and effects that describe how they affect states at T + 1. A fluent holds at T if it was initiated by an event occurrence at T -1. A fluent which is true at T continues to hold until the occurrence of an event which terminates it. An event in our framework represents an action which is described in Section 3. The axioms of the event calculus is presented below.

negative ( neg ( F ) ) : -effect (E , neg ( F ) ) . initiates (E ,F , T ) : -effect (E , F ) , occurs (E , T ) , not negative ( F ) . terminates (E ,F , T ) : -effect (E , neg ( F ) ) , occurs (E , T ) , time ( T ) . clipped (F , T ) : -terminates (E ,F , T ) . holds (F ,0) : -initially ( F ) . holds (F , T ) : -initiates (E ,F ,T -1) , time ( T ) . holds (F , T ) : -holds (F ,T -1) , not clipped (F ,T -1) , time ( T ) .

: -occurs (E , T ) , prec (F , E ) , not holds (F , T ) , act ( E ) , time ( T ) . 0 { occurs (E , T ) } 1 : -act ( E ) , time ( T ) ,T < maxtime . : -occurs ( E1 , T ) , occurs ( E2 , T ) , E1 != E2 .

Listing 1.3: Event calculus axioms

The choice rule 0 {performs(E, T)} 1 :-act(E), time(T),T<maxtime. is used to exempt the perform/2 predicate from minimization in ASP, this is the generator part that we use to solve a planning problem. The rule :-performs(E1,T), performs(E2,T) ,E1!= E2. means that events can not occur at the same time.

Note that ASP programs are represented as a finite set of rules where the head and body of the rules are composed of atoms which are equivalent to classical FOL(under the form of clauses with universally quantified variables). Variables in ASP are strings that begin with a capital lette, and they are all universally quantified.

We consider an agent that handles personal data processing. We are concerned about the compliance of the agents' actions with GDPR. In order to model both requirements of the planning domain and compliance checking, we built a modular framework with 2 components. The first one is the planning module that contains the specification of storage, and personal data in the system and the agents' actions. Each action describes a transformation on data or changes its storage. Given an initial state and a goal state, this module generates all the possible plans which satisfy the goal. By plan, we refer to a sequence of processing on personal data. The second module (Compliance engine) checks if each plan is compliant with both regulatory norms and data subject's given consent, and can provide explanation of missing obligations in the case of non-compliance. Figure 1 illustrates the structure of the framework.

A Use Case Model

We describe our framework by implementing it on a use case model. An international company operates in multiple European countries and United States as well. The company has several sectors for providing services to customers. Each sector owns a server for storing personal data. The servers are connected through an internal network and can transmit data among each other. One of the servers is a computing server in which the company analyze customers data for various purposes. The company has also a partner as a data processor which delivers analytic services to the company. Figure 2 illustrates the connection between servers of the company and its partner processor, as well as their location.

In order to provide services, the company needs to analyze customers data and use its result. When a sector requests the outcome of a particular analysis, a sequence of processing should be performed to provide the result to it's corresponding server. We implement our framework in this scenario to design an agent Fig. 2: Connection among servers to automatically generate a sequence of data processing to provide the requested output on a data, and check for the compliance of generated sequences.

Planning

The key challenge in the design of the planning domain is formalizing actions, states and domain knowledge in a way that enables for both planning and compliance checking. We assign GDPR related attributes to domain objects to use it for compliance checking. We describe the main parts of the planning domain.

Storage A storage in our framework basically represents anything capable of storing data and processing it. e.g. servers, cloud space etc. We use the storage to represent a server in our planning domain. We also use connected/2 predicate to represent that there is a connection between 2 storage. For example, below ASP formalization means that s1, s2, and s3 are storage and there is a connection between s1 and s2, and s1 and s3, meaning that they can transmit data. storage ( s1 ) . storage ( s2 ) . storage ( s3 ) . connected ( s1 , s2 ) . connected ( s1 , s3 ) .

The knowledge about other servers, and the connection between them, has been formalized the same way. In order to assess the compliance of these actions, we need the information about the action itself as well as the other complementary information that are concerned with the GDPR. For example, the below code, shows how we represent the controller of the storage s6 and s7 and the location of s1 and s2. has ( s6 , controller , aProcessor ) . has ( s7 , controller , aCompany ) . has ( s1 , location , us ) . has ( s2 , location , eu ) . s4 and s6 are computing servers capable of analyzing data for various purposes. The knowledge about supported purposes on each one can be represented in the following way. Data A personal data is represented by a resource. Each resource belongs to a data subject and has a category. Consider two resources d1 and d2 where they have categories Purchases and Spending Habit and Service Consumption Behavior this is represented in the following way in ASP.

resource ( d1 ) . resource ( d2 ) . has ( d1 , dataCategory , p u r c h a s e s A n d S p e n d i n g H a b i t ) . has ( d2 , dataCategory , s e r v i c e C o n s u m p t i o n B e h a v i o r ) .

When performing actions on resources, they either move to another storage or transform into a new data. We need to represent these data manipulations in our domain. We define the predicate data which represents any personal data either a resource or the output of analysis process on this resource with a certain purpose. If the attributes are static we represent them as facts and if they are dynamic we represent them by fluents. Attributes like storage of the data or the content of a storage are effected by actions.

Actions Specification The agent action in our domain represents a data processing. It supports transfer and analysis processing of personal data with several purposes. A transfer action in our domain is characterized by the data, its current location, the destination and purpose of the transfer. In order to perform analysis action we require the data, and the storage where the processing is taking place and the purpose of the analysis as well. We formalize the knowledge about agents actions as follows: Each action should be specified by its preconditions and effects. A transfer action changes the storage of the data, or equivalently, it modifies the content of the origin and destination storage. This is captured by the fluent hasData(A ,D) predicate, which represents that storage A has data D.The analysis action transforms the personal data into a new data, which is the output of this analysis. Below, we represent the effects and preconditions of these actions.

p r e c ( h a s D a t a (A, D) , t r a n s f e r (D, A, B , P) ) :-a c t ( t r a n s f e r (D, A, B , P) ) . e f f e c t ( t r a n s f e r (D, A, B , P) , h a s D a t a (B , D) ) :-a c t ( t r a n s f e r (D, A, B , P) ) . e f f e c t ( t r a n s f e r (D, A, B , P) , n e g ( h a s D a t a (A, D) ) ) :-a c t ( t r a n s f e r (D, A, B , P) ) . p r e c ( h a s D a t a (A, D) , a n a l y z e (D, A, P) ) :-a c t ( a n a l y z e (D, A, P) ) . e f f e c t ( a n a l y z e (D, A, P) , h a s D a t a ( A, a n a l y s i s O u t p u t (D, P)

) ) :-a c t ( a n a l y z e (D, A, P) ) . e f f e c t ( a n a l y z e (D, A, P) , n e g ( h a s D a t a (A, D) ) ) :-a c t ( a n a l y s e (D, A, P) ) .

As an example, we describe the effects and preconditions of analyze action. prec( hasData(A,D), analyze(D,A,P)) means that in order to perform the action, analyze (D,A,P) the fluent hasData(S,D) should hold, meaning that the corresponding data should be present on the corresponding storage. When the action is performed, the data transforms into the output and is represented by analysisOutput(D,P) . The last line effect(analyze(D,A,P), neg( hasData(A,D) )) means that after the action is performed, the output data would be replaced by the input data. The predicateneg( hasData(A,D) )) indicates the negative effect of the action, which is the input data in no longer on the corresponding storage (see event calculus axioms in listing 1.3).

Compliance Engine

This module contains required elements for compliance checking against regulative norms and data subject's consent. For this purpose, it should be fed with legal specifications and formalization of the given consent. Legal specification contains organizational measures, the legal basis of the processing, and the duties defined for processing. The compliance engine has 3 main parts, the first part assigns legal information to actions based on the legal specifications. It then checks for the compliance against regulatory obligations in the next one. In the last part can check the compliance of these actions with the data subject's given consent. Each part is described below.

Actions as Business Policy

An action should be associated with the legal information similar to the attributes of a business policy in SPECIAL (see the example of a business policy in listing 1.1). The legal information associated with an action should match with the description of a business policy to be compatible with the underlying policy language. The below example shows how a transfer action is associated with the legal information using the format has( Action, GDPR_attribute, Value). For example, the knowledge about legal basis at line 6 or appropriate safeguards for a personal data transfer at line 7 and 8. Notice that only a fragment of the associated attributes are shown below, you can find the complete list in the code repository 1 .

has ( transfer (D ,A ,B , P ) , dataCategory , X ) : -act ( transfer (D ,A ,B , P ) ) , has (D , dataCategory , X ) . has ( transfer (D ,A ,B , P ) , storage , B ) : -act ( transfer (D ,A ,B , P ) ) . has ( transfer (D ,A ,B , P ) , purpose , P ) : -act ( transfer (D ,A ,B , P ) ) . has ( transfer (D ,A ,B , P ) , recipient , X ) : -act ( transfer (D ,A ,B , P ) ) , has (B , controller , X ) . s y s t e m _ l e g a l _ b a s i s ( a r t 6 _ 1 _ a _ C o n s e n t ) . has ( transfer (D ,A ,B , P ) , legalBasis , X ) : -act ( transfer (D ,A ,B , P ) ) , s y s t e m _ l e g a l _ b a s i s ( X ) . t r a n s f e r _ s a f e g u a r d ( s4 , s1 , a r t

GDPR Regulatory Obligations

We define necessary predicates and axioms to produce a straightforward translation of the GDPR regulatory obligations encoded in SPECIAL policy language and support for explainability in the case of non-compliance. As an example, the obligation at bottom level, Article 6-1(lawful processing) presented in 2. a r t 6 _ 1 _ f _ L e g i t i m a t e I n t e r e s t ) . fulfills (O , a r t 6 _ 1 _ L e g a l B a s i s ) : -has (O , legalBasis , X ) , a r t 6 _ 1 _ L e g a l B a s i s ( X ) , act ( O ) .

Each regulation is named after its reference in the GDPR text, part of the current supported obligations in this module are presented as by the predicate regulation. Where gdpr_Requirements represents the obligations at the top level. regulation ( a r t 6 _ 1 _ L e g a l B a s i s ; a r t 6 _ l a w f u l P r o c e s s i n g ; a r t 1 2 _ 2 2 _ S u b j e c t R i g h t s ; c h a p 3 _ R i g h t s O f D a t a S u b j e c t s ; c h a p 2 _ L a w f u l P r o c e s s i n g ; a r t 9 _ s e n s i t i v e D a t a ; g d p r _ R e q u i r e m e n t s ) .

In the SPECIAL policy language, the obligation at the bottom level are nested to form the top level obligation. The regulations are combined using the operators ObjectUnionOf and ObjectIntersectOf. We capture the same semantic by the predicates inUniounOf and inIntersectOf. For example, the listing 2.1 is translated as follows inUnionOf ( a r t 6 _ L a w f u l P r o c e s s i n g , c h a p 2 _ L a w f u l P r o c e s s i n g ) . inUnionOf ( art9_SensitiveData , c h a p 2 _ L a w f u l P r o c e s s i n g ) . inUnionOf ( art10_CriminalData , c h a p 2 _ L a w f u l P r o c e s s i n g ) .

The predicate inUnionOf/2 is defined as below. It means that if an action P fulfills the obligation set of R2, and R2 is in union set of R1 then, it also fulfills the obligation of R1. fulfills (P , R1 ) : -fulfills (P , R2 ) , inUnionOf ( R2 , R1 ) , act ( P ) .

An action is compliant if it fulfills all obligations of the fraction of the GDPR at the top level. A plan contains several actions, and it is possible that only a certain operation violates the compliance of the plan. In this case we are interested to know which missing obligation caused the non-compliance, in order to do so we use the predicate missing/2 in the following ASP rule, it indicates that the obligations of a certain article are missed. missing1 (P ,R , R ) : -not fulfills (P , R ) , regulation ( R ) , act ( P ) , occurs (P , _ ) . missing1 (P , R1 , R2 ) : -not fulfills (P , R2 ) , upperClass ( R3 , R2 ) , missing1 (P , R1 , R3 ) , regulation ( R1 ) , regulation ( R2 ) . missing (P , R ) : -missing1 (P ,R , g d p r _ R e q u i r e m e n t s ) , not a u x i l i a r y R e g u l a t i o n ( R ) . Data Subject's Consent Suppose that when collecting personal data, the user has given explicit consent for transferring his Purchases and Spending Habit data for the purpose of marketing. Based on this consent, the data can only be disclosed to aCompnay, and it should be stored only in Europe. We translate this consent using the same format as listing 1.2. Note that SPECIAL also supports time intervals for the validity of the consent, but we do not support it here. In our scenario, the data subject has also given his consent to analyze processing with same attributes.

has ( c2 , dataCategory , s e r v i c e C o n s u m p t i o n B e h a v i o r ) . has ( c2 , processing , transfer ) . has ( c2 , purpose , marketing ) . has ( c2 , recipient , aCompany ) . has ( c2 , storageLocation , eu ) .

In our modeling, a processing is compliant with the given consent if it has the same attributes as the action. We check for the compliance of an action with the given consent using the following set of rules. It basically states that valid consent of an operation is satisfied if there is a coherent consent for it; and an action is coherent with a consent if there is no difference between the attributes of the consent and the operation. We capture it by the predicate validConsentSatisfied that is true when there is coherent consent for it. non_coherent (P , C ) : -has (P ,A , Z1 ) , has (C , A , Z2 ) , Z1 != Z2 , act ( P ) , consent ( C ) . v a l i d C o n s e n t S a t i s f i e d ( P ) : -not non_coherent (P , C ) , act ( P ) , consent ( C ) .

Evaluation

Once we have modeled our domain knowledge, the planning module can be used to generate plans by providing an initial state and a goal state. A plan is generated to deliver the result of processing of personal data to the server asking for it. Consider that data d1 is initially stored in the server s1. We represent this initial state by initially( hasData(s1,d1)).

There is a request from server s4 for the results of the analysis on data d1 with the purpose marketing. We represent this request by requestAnalysis(s4, d7 , marketing). This request is then translated into a goal for the system that the output of this analysis should be stored on the storage asking for it. holds ( goal , T ) : -holds ( hasData (A , anal ysisOutp ut (D , P ) ) , T ) , r eq u es tA na l ys is ( A ,D , P ) . : -not holds ( goal , maxtime ) .

After providing the initial state and a goal state, all the possible plans are generated to satisfy the given request. Plans are included in Table 1. Note that all these sequence of actions are generated regardless of their compliance. Each plan is a set of actions presented by the predicate perform/2 which indicates the action and the time step in which it can be performed.

Having the plans generated by the previous module, the compliance engine can distinguish the compliant plans with the non-compliant ones and also provide a simple explanation for non-compliance by referring to the missing obligations. A plan is compliant if all the actions in that plan are compliant. Below we show the compliance checking result in two scenarios; Compliance checking with (i) data subject's given consent and (ii) GDPR regulatory norms. In both cases the initial state and the goal state are the same and the same plans are generated by the planning module (shown in Table 1), therefore the compliance engine assess the compliance of the identical plans but with different legal restrictions.

Consent compliance checking

In this scenario the customer has given a customized set of consent for various data processing. In particular we suppose that the data subject has given her consent only for internal transfers in EU so the compliance engine distinguish non-compliant plans if they are compatible with data subject's given consent. Table 2 presents the compliance of each plan as well as the explanation of the missing obligations. All the plans are generated automatically by the personal data managing agent. The process of compliance checking is also done automatically in the second module. Plan 1 and 3 are compliant since they fulfill all the obligation set forth of GDPR as well as the compliance with consent. Plan 2 and 4 are both noncompliant because of the same reason. The action transfer(d1,s1,s3,marketing) lacks the obligation of art12_22_SubjectRights since the transfer action does not match with the provided consent. When the obligations of a regulation are missed, it also causes that the obligations of the super class regulations to fail. In this case the action transfer(d1,s2,s1,marketing) misses the obligations of chap3_RightsOfDataSubjects , and gdpr_Requirements as they are the top classes of regulations in the policy formalization. Two other regulations have been reported as missed obligations, exceptions_as_per_Art23 and chap9_Derogations, this is because if the obligations of these regulations is fulfilled, it causes the transfer action to comply with GDPR.

Compliance checking against GDPR regulatory norms In this scenario we suppose that all the necessary consent is provided, so consent is no more a restricting constraint. We check the compliance of plans against GDPR regulatory norms, in particular obligations of GDPR Chapter 5 (Transfers of personal data to third countries or international organisations). According to SPECIAL policy language2 a transfer to a third country is only possible if it is not among the unauthorized transfers by Union law Article 48 (Transfers or disclosures not authorised by Union law ) and is equipped with measures to assure a secure data transfer; these measures could be one of the appropriate safeguards as in Article 46 (Transfers subject to appropriate safeguards). Again we aim at checking the compliance of plans shown in Table 1, with the assumption that all the necessary consent is provided but no safety measures exist among the servers outside the EU (third countries) and the servers located in EU. The resulting compliance report is indicated in As shown in Table 3 plan 2 and 4 are not compliant, since the action transfer( d1,s2,s1,marketing) miss the required obligations of GDPR Chapter 5. The principal missed elements are adequateLevelOfProtection_as_per_Art45, appropriateSafeguards_as_per_Art46 or art49_Derogations. The transfer action could be compliant if certain regulations among missed ones are satisfied.

Related works

Since the adoption of the GDPR, several tools and techniques have been introduced to facilitate the compliance assessment for data controllers and processors. Some of these methods are in the form of a questionnaire which evaluates the compliance of data processor and controllers e.g. Microsoft Trust Center, Agarwal et al. [START_REF] Agarwal | Legislative compliance assessment: framework, model and gdpr instantiation[END_REF], but these methods do not support automated compliance checking.

Others focus on building an ontological concept of GDPR, e.g. PrOnto a privacy ontology Palmirani et al. [START_REF] Palmirani | Legal ontology for modelling gdpr concepts and norms[END_REF] which relays on LegalRuleML Palmirani et al. [START_REF] Palmirani | Legalruleml: Xml-based rules and norms[END_REF] for legal reasoning and compliance checking of business processes. These methods can be used to make a repository of rules based on regulative and constitutive norms (cf. Robaldo et al. [START_REF] Robaldo | Formalizing gdpr provisions in reified i/o logic: the dapreco knowledge base[END_REF]). However, they provide a machinereadable representation of GDPR norms suitable for legal reasoning. One of our aims as future work is to integrate use a comprehensive ontology of GDPR norms with a legal reasoning engine.

Another body of works develop policy languages to enable the compliance checking of business processes De Vos et al. [START_REF] Vos | Odrl policy modelling and compliance checking[END_REF], Bonatti et al. [START_REF] Bonatti | Machine understandable policies and gdpr compliance checking[END_REF]. The latter is based on the W3C Data Privacy Vocabulary and Controls Community Group (DPVCG) Pandit et al. [START_REF] Pandit | Creating a vocabulary for data privacy[END_REF] that is a vocabulary towards interoperability in the context of data privacy. De Vos et al. [START_REF] Vos | Odrl policy modelling and compliance checking[END_REF] introduce an ODRL policy pipeline to represent GDPR requirements and business policies. They then translate these representations in answer set programming and use it to check for the compliance of a business policy with GDPR regulatory obligations.

A number of works focus on integrating policies in a dynamic environment. Bandara et al. [START_REF] Bandara | Using event calculus to formalise policy specification and analysis[END_REF] present a method for transforming both, policy and system behavior specifications into a formal notation that is based on Event Calculus.

However, they use it for detecting conflicts in the system. In the privacy domain, Le Métayer and Rauzy [START_REF] Métayer | Capacity: an abstract model of control over personal data[END_REF] propose a formal framework to specify the notion of control over personal data and to reason about it, but it does not support compliance mechanism with any data protection regulation.

The methodology by De Vos et al. [START_REF] Vos | Legal modelling and reasoning using institutions[END_REF] uses a domain-specific language called InstAL based on ASP which is fairly similar to event calculus. They use InstAL to model events and time-varying properties in the system but not to generate sequences of actions to satisfy a given goal. Instead, they provide the program with the performed actions and are mainly interested in the evolution of the governing norms when an action takes place by an agent. However, in our current work norms are assumed constant and we use them to distinguish compliant and non-compliant plans. Adding support for time-varying norms is considered as a future extension to the current work.

Conclusion and future work

The goal in the current paper was two-fold (i) designing an AI agent that generates sequence of data processing or plans in order to satisfy a given goal, (ii) compliance checking of these plans with GDPR. In order to fulfill these goals, we presented a framework for planning in the privacy domain and compliance checking with GDPR. We made use of event calculus to formalize agent actions on personal data, and time-varying properties of the system. In order to formalize GDPR obligation set and data subjects consent, we chose SPECIAL policy language. We described how the knowledge of the planning domain and legal knowledge can be represented and combined together in our framework. We presented two scenarios in Section 4 and showed how our framework can be used to achieve the mentioned goals.

Our future goal is to design an AI agent with real-time legal and ethical supervisors concerning personal data protection. This work is highly dependent on the legal ontology or the policy language that we use to represent GDPR requirements. In the current paper we use SPECIAL as the underlying policy language, which is a simple machine-readable policy that does not support deontic operations.

Our ongoing work includes using a more comprehensive legal ontology like, PrOnto Palmirani et al. [START_REF] Palmirani | Legal ontology for modelling gdpr concepts and norms[END_REF] or other policy languages like ODRL based one by De Vos et al. [START_REF] Vos | Odrl policy modelling and compliance checking[END_REF], and cover more GDPR articles in the design of the system. The current work assess the compliance in a static manner, i.e., it does not consider the evolution of norms in real-time as in De Vos et al. [START_REF] Vos | Legal modelling and reasoning using institutions[END_REF], adding support for more complex legal models is on other aspect of this work which we are trying to improve.

Other future works include developing our framework to implement more complex data processing scenarios cable to handle specific ethical issues concerning data protection an adding support for deontic operators and handle conflicts in real-time.

O b j e

  c t I n t e r s e c t i o n O f ( ObjectSomeValuesFrom ( s p l : h a s D a t a s v d : p u r c h a s e s A n d S p e n d i n g H a b i t ) ObjectSomeValuesFrom ( s p l : h a s P r o c e s s i n g s v p r : A n a l y z e ) ObjectSomeValuesFrom ( s p l : h a s P u r p o s e s v p u : M a r k e t i n g ) ObjectSomeValuesFrom ( s p l : h a s R e c i p i e n t svr:aCompany ) ObjectSomeValuesFrom ( s p l : h a s S t o r a g e O b j e c t I n t e r s e c t i o n O f ( s p l : h a s L o c a t i o n s v l : E U s p l : h a s D u r a t i o n s v d u : I n d e f i n i t e l y

O

  b j e c t I n t e r s e c t i o n O f ( ObjectSomeValueFrom ( h a s p u r p o s e c r e a t e P e r s o n a l i z e d R e c o m m e n d a t i o n s ) ObjectSomeValueFrom ( h a s d a t a s e r v i c e C o n s u m p t i o n B e h a v i o r ) ObjectSomeValueFrom ( h a s p r o c e s s i n g T r a n s f e r ) ObjectSomeValueFrom ( h a s r e c i p i e n t aCompany ) ObjectSomeValueFrom ( h a s s t o r a g e O b j e c t I n t e r s e c t i o n O f ( ObjectSomeValueFrom ( h a s l o c a t i o n : E U )

Fig. 1 :

 1 Fig. 1: Modular structure

  has ( s4 , a na ly s is Pu rp o se , marketing ) . has ( s4 , a na ly s is Pu rp o se , p e r s o n a l i s e d A d v e r t i s i n g ) . has ( s6 , a na ly s is Pu rp o se , o p t i m i s a t i o n F o r C o n t r o l l e r ) .

  data ( D ) : -resource ( D ) . data ( analy sisOutpu t (D , P ) ) : -resource ( D ) , purpose ( P ) .

  act ( transfer (D ,A ,B , P ) ) : -data ( D ) , storage ( A ) , storage ( B ) , purpose ( P ) , connected (A , B ) , A != B . act ( analyse (D ,A , P ) ) : -data ( D ) , storage ( A ) , purpose ( P ) , has (A , a na ly si s Pu rp os e ,P ) .

  4 6 _ 2 _ e _ A p p r o v e d C o d e O f C o n d u c t ) . has ( transfer (D ,A ,B , P ) , measures , X ) : -act ( transfer (D ,A ,B , P ) ) , t r a n s f e r _ s a f e g u a r d (A ,B , X ) .

  ,s2,s3,marketing) transfer(d1,s3,s4,marketing) 1 analyse(d1,s4,marketing) transfer(analyseOut(d1,marketing),s4,s7,marketing) transfer(analyseOut(d1,marketing),s7,s5,marketing) transfer(d1,s2,s1,marketing) transfer(d1,s1,s4,marketing) 2 analyse(d1,s4,marketing) transfer(analyseOut(d1,marketing),s4,s7,marketing) transfer(analyseOut(d1,marketing),s7,s5,marketing) transfer( d1, s2, s3, marketing) transfer( d1, s3, s4, marketing) 3 analyse( d1, s4, marketing) transfer( analyseOut(d1, marketing), s4, s3, marketing) transfer( analyseOut(d7, marketing), s3, s5, marketing) transfer(d1,s2,s1,marketing) transfer(d1,s1,s4,marketing) 4 analyse(d1,s4,marketing) transfer(analyseOut(d1,marketing),s4,s3,marketing) transfer(analyseOut(d1,marketing),s3,s5,marketing)

  1, has been translated into ASP using the predicate fulfills/2. This rule means that an action O fulfills the obligations of article 6-1, if it has a legal basis as defined in the list. Note that in, ASP pred(a;b) is equivalent to pred(a) and pred(b).

	a r t 6 _ 1 _ L e g a l B a s i s ( a r t 6 _ 1 _ a _ C o n s e n t ;
	a r t 6 _ 1 _ b _ C o n t r a c t ;
	a r t 6 _ 1 _ c _ L e g a l O b l i g a t i o n ;
	a r t 6 _ 1 _ d _ V i t a l I n t e r e s t ;
	a r t 6 _ 1 _ e _ P u b l i c I n t e r e s t ;

Table 1 :

 1 Automatic generated plans.

Table 2 :

 2 Automatic compliance checking of plans (Consent).

Table 3

 3

	Plan Compliance	Explanation
	1 and 3	Yes	-
			missing(transfer(d1,s2,s1,marketing),chap5_DataTransferToThirdCountry)
			missing(transfer(d1,s2,s1,marketing),adequateLevelOfProtection_as_per_Art45)
	2 and 4	No	missing(transfer(d1,s2,s1,marketing),appropriateSafeguards_as_per_Art46)
			missing(transfer(d1,s2,s1,marketing),art49_Derogations)
			missing(transfer(d1,s2,s1,marketing),chap9_Derogations)
			missing(transfer(d1,s2,s1,marketing), gdpr_Requirements)

Table 3 :

 3 Automatic compliance checking of plans (obligations of GDPR chapter 5)

https://gitlab.lip6.fr/taheri/planning-compliance-mechanism-policies. git.

link to the documentations: https://specialprivacy.ercim.eu/platform/ pilots-policies-and-the-formalization-of-the-gdpr.


Amine Ouhechou

Nathalie Philippon

Béatrice Morel

Validation and comparison of incoming solar radiation satellite databases on the Atlantic coast of Central Africa

come   L'archive ouverte pluridisciplinaire

Validation and comparison of incoming solar radiation satellite databases on the

Atlantic coast of Central Africa.

Amine OUHECHOU, Nathalie PHILIPPON and Béatrice MOREL



  The Atlantic coast receives the least quantity of solar radiation  Satellite products from MSG are the brightest • Results and Discussion Hovmöller diagram  The minimum of solar radiation is observed in June-August  CLARA and ERA5 have a second minimum during the October-November rainy season The cycle is well reproduced by all the products ( R>0,75 )  CERES underestimates and the other products overestimate  The maximum in February-March and the minimum in July-

the mean spatial and temporal variations of solar radiation (light availability for tree photosynthesis  Document the specificity of the Atlantic coast  Determine which satellite estimate(s) (in the absence of sufficient in-situ measurements) is the most suitable for the study of solar radiation on the Atlantic coast. Data set Spatial resolution Temporal resolution Temporal range Satellite orbit type

	CERES-EBAF	1° × 1°	Monthly	2000-03 / 2019-11	Terra + Aqua	Heliosynchronous orbit
	CERES-SYN1deg	1° × 1°	Hourly	2000-03 / 2019-11	Terra + Aqua	Heliosynchronous orbit
	Ré-analyses ERA5	0.25° × 0.25°	Monthly	1979-01 / 2020-12	---	---
	CM SAF-CLARA-A2	0.25° × 0.25°	Monthly	1982-01 / 2015-12	AVHRR sensors on series of NOAA satellites and the METOP satellite.	polar orbit
	CAMS-JADE	0.2° × 0.2°	15 minutes	2005-01 / 2018-12	MVIRI/SEVIRI on METEOSAT MSG	geostationary orbit
	CM SAF-SARAH 2	0.05° × 0.05°	Hourly	1983-01 / 2020-12

• Objectives

 Analyze

MVIRI/SEVIRI on METEOSAT MSG geostationary orbit

Availability period

Pokola

•

Results and Discussion

Monthly variation of bias results.

CERES-SYN1deg

• Conclusion

The satellite products represent well the spatial distribution, and reproduce well the mean annual cycle of incident solar radiation