Danny Hermelin
email: hermelin@mpi-inf.mpg.de

Romeo Rizzi
email: rrizzi@dimi.uniud.it

Stéphane Vialette
email: vialette@univ-mlv.fr

Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph

The intersection number of a graph G is the minimum size of a ground set S such that G is an intersection graph of some family of subsets F ⊆ 2 S . The overlap number of G is defined similarly, except that G is required to be an overlap graph of F. In this paper we show two algorithmic aspects concerning both these graph invariants. On the one hand, we show that the corresponding optimization problems associated with these numbers are both APX-hard, where for the intersection number our results hold even for biconnected graphs of maximum degree 7, strengthening the previously known hardness result. On the other hand, we show that the recognition problem for any specific intersection graph class (e.g. interval, unit disc, string, ...) is easy when restricted to graphs of fixed bounded intersection or overlap number.

Introduction

An intersection graph is a graph that represents the pattern of intersections of a family of sets. Any undirected graph G may be represented as an intersection graph: For each vertex of G, form a set consisting of the edges incident to this vertex; then two such sets have a nonempty intersection if and only if the corresponding vertices share an edge []. Erdös, Goodman, and Pósa [START_REF] Erdös | The intersection of a graph by set intersections[END_REF] provided a construction that is more efficient in which the total number of set elements is at most n 2 /4, where n is the number of vertices in the graph. Many important graph families can be described as intersection graphs of more restricted types of set families, in particular sets corresponding to geometric objects. Examples of such graph classes are interval graphs (intersection graphs of intervals on the real line), circle graphs (intersection graphs of chords in a circle), unit disc graphs (intersection graphs of unit discs in the plane), and string graphs (intersection graphs of simple curves in the plane).

The intersection number of G, denoted i(G), is defined to be the minimum cardinality of a (ground) set S such that G is an intersection graph of a family of subsets F ⊆ 2 S of S. In [START_REF] Erdös | The intersection of a graph by set intersections[END_REF], it was shown that i(G) also equals the minimum number of complete subgraphs needed to cover the edges of G. This latter number is known as the edge-clique cover number of G, and is denoted θ(G). (The best general reference is [START_REF] Mckee | Topics in intersection graph theory[END_REF].) Computing θ(G) and i(G) is NP-hard [START_REF] Kou | Covering graphs by cliques with regard to keyword conflicts and intersection graphs[END_REF][START_REF] Orlin | Contentment in graph theory: Covering graphs with cliques[END_REF], even when restricted to planar graphs [START_REF] Chang | On the tree-degree of graphs[END_REF] or graphs with maximum degree 6 [START_REF] Hoover | Complexity of graph covering problems for graphs of low degree[END_REF]. It is polynomial-time solvable for chordal graphs [START_REF] Ma | Clique covering of chordal graphs[END_REF], graphs with maximum degree 5 [START_REF] Hoover | Complexity of graph covering problems for graphs of low degree[END_REF], line graphs [START_REF] Orlin | Contentment in graph theory: Covering graphs with cliques[END_REF], and circulararc graphs [START_REF] Hsu | Linear time algorithms on circular-arc graphs[END_REF]. By way of contrast, it is not approximable within ratio n ε for some ε > 0 unless P = NP [START_REF] Lund | The approximation of maximum subgraph problems[END_REF], and so far nothing better than a polynomial ratio of O(n 2 (log log n) 2 (log n) 3 ) is known [START_REF] Ausiello | Complexity and Approximation: Cominatorial optimization problems and their approximability properties[END_REF]. As for its parameterized complexity, computing θ(G) is fixed-parameter tractable under the standard parameterization [START_REF] Gramm | Data reduction and exact algorithms for clique cover[END_REF]. Guillaume and Latapy [START_REF] Guillaume | Bipartite structure of all complex networks[END_REF] argue that computing θ(G) is very widely applicable to discover underlying structure in complex real-world networks, while [START_REF] Nor | Mod/resc parsimony inference[END_REF] give a bioinformatic application for this problem.

The overlap model for graph representations arose much later and is not as well studied [START_REF] Cranston | Overlap number of graphs[END_REF]. The overlap graph of a family of sets F = {S 1 , S 2 , . . . , S n }, denoted O(F), is the graph having F as vertex set with S i adjacent to S j if and only if S i and S j intersect and neither set is contained in the other, i.e., S i ∩ S j = ∅, S i \ S j = ∅, and S j \ S i = ∅. Notice that some graph classes can play it both ways: A graph is an intersection graph of chords in a circle (i.e. circle graph) iff it is has an overlap representation using intervals on a line. The overlap number of a graph G, denoted ϕ(G), is the minimum size of the ground set in any overlap representation of G. The following upper bounds for the overlap number of a n-vertex graph are known [START_REF] Rosgen | Set representations of graphs[END_REF][START_REF] Rosgen | The overlap number of a graph[END_REF]: n + 1 for trees, 2n for chordal graphs, 10 3 n -6 for planar graphs, and n 2 /4 + n for general graphs. It was also observed that the overlap number of K n is the minimum ℓ such that a ℓ-set contains n pairwise incomparable sets, that the overlap number of C n is n -1, and that the overlap number of any caterpillar with at least 2 vertices if the number of vertices in the longest path. In [START_REF] Cranston | Overlap number of graphs[END_REF], it is shown among other results that an optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2.

The results in this paper are of twofold. In the first part of the paper, we consider the Intersection Number and Overlap Number problems, the optimization problems that ask to respectively determine the intersection and overlap number of a given input graph. We show that both problems are APX-hard. While for Intersection Number this was already known for general graphs [START_REF] Lund | The approximation of maximum subgraph problems[END_REF], our result proves this is the case also for graphs of maximum degree 7. Moreover, this result is used to show the APX-hardness of Overlap Number. In the second part of the paper, we show that for any intersection graph class G, i.e. any graph class defined by specifying the allowed intersection model, the recognition problem associated with G is linear-time solvable when restricted to graphs with bounded fixed intersection or overlap number.

Notations

Let G be a graph. We write V(G) for the set of vertices and E(G) for the set of edges of G. An adjacent vertex of a vertex u in a graph is a vertex that is connected to u by an edge. The neighborhood of a vertex u, denoted N G (u) or (when the graph is unambiguous) N (u), is the set of adjacent vertices to u. We let N [v] denote the set {v} ∪ N (v). The degree of a vertex u ∈ V(G), denoted d(u), is the number of vertices adjacent to u. The maximum degree of G, denoted by ∆(G), is the maximum degree of its vertices. A biconnected graph is a connected graph that is not broken into disconnected pieces by deleting any single vertex (and its incident edges). An edge-clique cover of G is any family

E = {Q 1 , Q 2 , . . . , Q k } of complete subgraphs of G such that every edge of G is in at least one of Q 1 , Q 2 , . . . , Q k .
The minimum cardinality of an edge-clique cover of G is denoted θ(G), and we write Edge-Clique Cover for the combinatorial problem of computing θ(G).

The Cartesian product G × H of graphs G and H is the graph such that the vertex set of G × H is the Cartesian product V(G) × V(H), and any two vertices (u, u ′ ) and (v,

v ′ ) are adjacent in G × H if and only if either u = v and u ′ is adjacent with v ′ in H, or u ′ = v ′ and u is adjacent with v in G. A column of G × H is the set of vertices {(u, u ′ ) : u ∈ V(G)} for some vertex u ′ ∈ V(H), and a row of G × H is the set of vertices {(u, u ′ ) : u ′ ∈ V(H)} for some vertex u ∈ V(G).
Observe that each row induces a copy of H, and each column induces a copy of G (see Figure 1). This terminology is consistent with a representation of G × H by the points of the |V(G)| × |V(H)| grid. (See Figure 1 for an illustration.) = Fig. 1. The cartesian products of two graphs.

Hardness of approximating i(G)

Since i(G) = θ(G) [START_REF] Erdös | The intersection of a graph by set intersections[END_REF], we prove hardness of approximation for bounded degree graphs in terms of edge-clique covers. Notice that this result will be the main ingredient of upcoming Proposition 2.

Proposition 1. Edge-Clique Cover is APX-hard for biconnected graphs with maximum degree 7.

Proof. The reduction is from Vertex Cover in cubic graphs, which is known to be APX-hard [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF][START_REF] Alimonti | Some APX-completeness results for cubic graphs[END_REF]. Let G be a cubic n-vertex graph. We construct a new graph H as follows. We represent each vertex u ∈ V(G) by a triangle T u with vertices u 0 , u 1 and u 2 in the new graph H. These n triangles are all vertex disjoint in H, and each of them can offer a different edge for three connections. Let us be more specific. For each vertex u ∈ V(G) with incident edges e u [0], e u [START_REF] Alimonti | Some APX-completeness results for cubic graphs[END_REF] and e u [START_REF] Ausiello | Complexity and Approximation: Cominatorial optimization problems and their approximability properties[END_REF] (the order is arbitrary), the edge

{u i , u i+1 (mod 3) } ∈ T u , 0 ≤ i ≤ 2, is devoted to the edge e u [i] ∈ E(G). Now, to represent an edge {u, v} ∈ E(G) in H, where {u i , u i+1 (mod 3) }, 0 ≤ i ≤ 2,
is the edge of the triangle T u devoted to representing {u, v}, and {v j , v j+1 (mod 3) }, 0 ≤ j ≤ 2, is the edge of the triangle T v devoted to representing {u, v}, we introduce two new vertices A u,v and B u,v and the 6 edges {u i , u i+1 (mod 3) }, 0 ≤ i ≤ 2, is the edge of the triangle T u devoted to representing {u, v}, and {v j , v j+1 (mod 3) }, 0 ≤ j ≤ 2, is the edge of the triangle T v devoted to representing {u, v}, we add the edge {u i , v j+1 (mod 3) } or {u i+1 (mod 3) , v j } (the choice is made so that these m additional edges form a matching). We refer the reader to Figure 2 for an illustration. Clearly |V(H)| = 9 2 n and |E(H)| = 27 2 n. Moreover, it follows from the construction that H is a biconnected graph with maximum degree 7.

{A u,v , u i }, {A u,v , v j }, {B u,v , u i+1 (mod 3) }, {B u,v , v j+1 (mod 3) }, and {u i , v j }.
We claim that G has a vertex cover of size k if and only if θ(H) ≤ k + 3m, where m = 3 2 n is the number of edges of G. Suppose G has a vertex cover V ′ ⊆ V(G) of size k. Construct an edge-clique cover E of H as follows. For each u ∈ V ′ , add T u to E. For each edge {u, v} ∈ E(G), let {u i , u i+1 (mod 3) }, i ∈ {0, 1, 2}, be the edge of triangle T u devoted to representing edge {u, v}, and {v j , v j+1 (mod 3) }, j ∈ {0, 1, 2}, be the edge of triangle T v devoted to representing edge {u, v}. Without loss of generality, assume {u i , v j+1 (mod 3) } ∈ E(H). Add the two cliques {u i , v j , A u,v } and {u i+1 (mod 3) , v j+1 (mod 3) , B u,v } to E. Furthermore, if u ∈ V ′ , add the clique {u i , v j , v j+1 (mod 3) } to E, and {u i , u i+1 (mod 3) , v j+1 (mod 3) } otherwise. Since V ′ is a vertex cover of G, it follows that E is an edge-clique cover of H of cardinality k + 3m.

For the reverse direction, let E be an edge-clique cover of H. Let {u, v} be any edge of G, and let {u i , u i+1 (mod 3) }, i ∈ {0, 1, 2}, be the edge of triangle T u de-voted to representing edge {u, v}, and {v j , v j+1 (mod 3) }, j ∈ {0, 1, 2}, be the edge of triangle T v devoted to representing edge {u, v}. Without loss of generality, assume {u i , v j+1 (mod 3) } ∈ E(H). If we let H u,v stand for be the subgraph of H induced by the subset {u i , u i+1 (mod 3) , A u,v , B u,v , v j , v j+1 (mod 3) }, we make the easy observations (see Figure 2) that (i) 4 cliques are needed to cover the edges of H u,v , and (ii) 3 cliques are needed to cover the edges of H u,v if {u i , u i+1 (mod 3) } or {v j , v j+1 (mod 3) } (possibly both) is removed. Therefore, |E| = 3m + k for some non-negative integer k ≤ m. But each triangle T w , w ∈ V(G), can be covered by 1 clique, and hence there is no loss of generality in assuming k ≤ n. Furthermore, there is no loss go generality in assuming that E satisfies the following property: for every edge {u, v} ∈ E(G), either T u or T v (possibly both) is in E. Let V ′ ⊆ V(G) be the subset defined as follows:

u ∈ V ′ if T u ∈ E. According to the above, if |E| = 3m + k for some non-negative integer k ≤ n, then |V ′ | = k is a vertex cover of G.
⊓ ⊔

Hardness of approximating ϕ(G)

This section is devoted to proving that there exists a constant c > 1 such that computing the overlap number of a graph is hard to approximate to within c.

Proposition 2. Overlap Number is APX-hard.
Proof. According to Proposition 1, there exists a constant c > 0 such that θ(G) cannot be approximated to within c (unless P = NP). We shall prove that a √ capproximation algorithm for Overlap Number would yield a c-approximation algorithm for Edge-Clique Cover Let G be a n-vertex graph for which we are asked to c-approximate θ(G). Without loss of generality, we assume that G has no isolated vertices and is biconnected (see Proposition 1). Let m be the smallest integer such that m ≥ n and m m-1 < c, and let K m be the complete graph on m vertices. Let H = K m × G be the cartesian product of K m by G. For the sake of simplicity, write V(K m ) = {u 1 , u 2 , . . . , u m } and V(G) = {v 1 , v 2 , . . . , v n }. We have divided the proof into a sequence of claims.

Claim 1. ϕ(H) ≤ n + m θ(G).

Proof (Of Claim 1). Let k = θ(G) and let E = {Q 1 , Q 2 , . . . , Q k } be a size-k edgeclique cover of G. To every node (u i , v j ) ∈ V(H), we associate the set S (u i ,v j ) defined as follows:

S (u i ,v j ) = {v j } ∪ {(u i , p) : v j ∈ Q p }.
Consider the family F = {S (u i ,v j ) : (u i , v j ) ∈ V(H)} defined over the ground set

X = (u i ,v j )∈V(H) S (u i ,v j ) = V(G) ∪ (V(K m ) × [k]),
where [k] is the set of the first k integers {1, 2, . . . , k}. Notice that |X| = n + km. We prove that O(F) and H are isomorphic graphs, thereby proving the claim. Indeed, let S (u i ,v j ) and S (ur,vs) be two subsets of F. We need to consider 3 cases.

-If u i = u r and v j = v s , then (u i , v j ) and (u r , v s ) are not adjacent vertices in H.

It can be easily verified that S (u i ,v j ) and S (ur,vs) are disjoint subsets, and hence S (u i ,v j ) and S (ur,vs) are not adjacent vertices in O(F).

-If u i = u r and v j = v s , then (u i , v j ) and (u r , v s ) are adjacent vertices in H since K m is a clique. Firstly, v j ∈ S (u i ,v j ) and v j ∈ S (ur,vs) since v j = v s , and hence S (u i ,v j ) ∩S (ur,vs) = ∅. Secondly, both v j ∈ S (u i ,v j ) \S (ur,vs) and v s ∈ S (ur,vs) \S (u i ,v j ) are non-empty (i.e., the two sets have some private element) since u i = u r and v j is not an isolated vertex of G. Therefore, S (u i ,v j ) and S (ur,vs) overlap, and hence S (u i ,v j ) and S (ur,vs) are adjacent vertices in O(F). -If u i = u r and v j = v s , then (u i , v j ) and (u r , v s ) are adjacent vertices in H if and only if {v i , v j } ∈ E(G). We have v j ∈ S (u i ,v j ) \ S (ur,vs) and v s ∈ S (ur,vs) \ S (u i ,v j ) (i.e., the two sets have some private element) Therefore, the two sets overlap if and only if v j and v j belong to a same Q p for some 1 ≤ p ≤ k, which amounts to saying that {v i , v j } ∈ E(G). Hence, S (u i ,v j ) and S (ur,vs) are adjacent vertices in

O(F) if and only if {v i , v j } ∈ E(G). ⊓ ⊔
For the reverse direction, we need the following technical claim that deals with containment in overlap representations of H.

Claim 2. Let (F = {S (u i ,v j ) : (u i , v j ) ∈ V(H)}, X) be an overlap representation of H.
If S (ur,vs) ⊂ S (u i ,v j ) for some vertices (u i , v j ) and (u r , v s ) of H, then S (up,vq) ⊂ S (u i ,v j ) for every vertex (u p , v q ) of H which is not adjacent to vertex (u i , v j ).

Proof (Of claim 2). First, if S (ur,vs) ⊂ S (u i ,v j ) then vertices (u r , v s ) and (u i , v j ) are not adjacent in H since (F, X) is an overlap representation of H. Now, let (u p , v q ) be any vertex of H distinct from (u r , v s ) that is not adjacent to (u i , v j ). Also, let H ′ be the graph obtained from H by deleting every vertex in the close neighborhood of vertex (u i , v j ). Notice that, since (u r , v s ) and (u p , v q ) are not adjacent to (u i , v j ) in H, they are both vertices of H ′ . We claim that there exists a path between vertices (u r , v s ) and (u p , v q ) in H ′ . Indeed, since G is biconnected there exists a path in G between vertices v s and v q that does not go through vertex v j , and hence there exists a path in H ′ between vertices (u r , v s ) and (u r , v q ). If u r = u p we are done. Otherwise, since each column of H ′ is a clique then the two vertices (u r , v q ) and (u p , v q ) are connected by an edge in H ′ .

To prove the claim it is now enough to show that S (up,vq) ⊂ S (u i ,v j ) for any vertex (u p , v q ) of H that is adjacent to (u r , v s ) but not to (u i , v j ). The proof follows from an easy contradiction. Suppose S (up,vq) ⊂ S (u i ,v j ) . Since S (up,vq) = ∅ (H does not contain any isolated vertex), then there exists x ∈ X such that x ∈ S (up,vq) and x / ∈ S (u i ,v j ) , and hence S (up,vq) \ S (u i ,v j ) = ∅. Furthermore, (u p , v q ) and (u r , v s ) are adjacent vertices in H, and hence (since S (up,vq) and S (ur,vs) have to overlap) there exist x ′ , x ′′ ∈ X such that (i) x ′ ∈ S (up,vq) and x ′ ∈ S (ur,vs) , and (ii) x ′′ / ∈ S (up,vq) and x ′′ ∈ S (ur,vs) . But S (ur,vs) ⊂ S (u i ,v j ) , and hence x ′ ∈ S (u i ,v j ) and x ′′ ∈ S (u i ,v j ) . Then it follows that S (u i ,v j ) \ S (up,vq) = ∅ and S (up,vq) ∩ S (u i ,v j ) = ∅, and hence S (up,vq) and S (u i ,v j ) overlap. This is the sought contradiction since this would result in (u p , v q ) and (u i , v j ) being adjacent in H.

⊓ ⊔

We are now ready for the reverse direction of the reduction.

Claim 3. θ(G) ≤ ϕ(H) -n -1 m -1 + 7.
Proof (Of claim 3). Let (F = {S (u i ,v j ) : (u i , v j ) ∈ V(H)}, X) be an overlap representation of H. Suppose that there exists some subset S (u i ,v j ) ∈ F that strictly contains at least one set of F. Then, according to Claim 2, S (u i ,v j ) contains all subsets S (ur,vs) ∈ F such that u i = u r and v j = v s (i.e., S (u i ,v j ) contains all those subsets of F that are associated to vertices of H that are not in the same row nor column of vertex (u i , v j )). Furthermore, if there exist subsets S (ur,vs) , S (up,vq) ∈ F distinct from S (u i ,v j ) such that S (ur,vs) ⊂ S (up,vq) , then u i = u p or v j = v q (i.e., vertex (u p , v q ) is on the same row or on the same column of vertex (u i , u j )). Indeed, assuming u i = u p and v j = v q , Claim 2 would yield to S (u i ,v j ) ⊂ S (up,vq) and S (u i ,v j ) ⊂ S (up,vq) , a contradiction. Now, let H ′ be the graph obtained from H by deleting all vertices (u r , v s ) such that u r = u i or v s = v j (i.e., deleting all vertices that are in the same row or column of vertex (u i , v j )). Also, let F ′ ⊆ F be those subsets of F that correspond to vertices of H ′ , and X ′ ⊆ X be the union of the subsets in F ′ (X ′ is the ground of F ′ ). Notice that F ′ is an overlap representation of H ′ where no subset being a subset of another, and that |X ′ | ≤ |S (u i ,v j ) | since every subset of F ′ is strictly contained in S (u i ,v j ) . Moreover, if we let G ′ stand for the graph obtained from G by deleting vertex v j we have

H ′ = K m-1 × G ′ . We now claim that θ(G ′ ) ≤ |X|-n-1 m-1 .
Indeed, consider the "edge-multi-coloring" procedure of H ′ defined by assigning to every edge e = {(u r , v s ), (u p , v q )} of H ′ the "colors" col(e) = S (ur,vs) ∩ S (up,vq) . Since F ′ is an overlap representation of H ′ , it follows that at least one color is assigned to every edge of H ′ . Furthermore, since no subset being a subset of another in F ′ , it follows that for every color c, {e ∈ E(H ′ ) : c ∈ col(e)} induces a clique in G ′ , and hence H ′ can be covered with at most |X| cliques. But the maximal cliques of H ′ are either columns (there are n -1 of these and at least n -1 vertical edges must have received a different color), or are contained in a single row and correspond to maximal clique of G. Therefore, m -1 disjoint copies of G ′ can be covered with at most |X|n -1 cliques.

This proves θ(G

′ ) ≤ |X|-n-1 m-1 . What is left is to prove θ(G) ≤ ϕ(H) -n -1 m -1 + 7. This follows from θ(G ′ ) ≤ |X|-n-1 m-1 and θ(G) ≤ θ(G ′ ) + ∆(G). ⊓ ⊔
Suppose, aiming at a contradiction, that there exists a √ c-approximation algorithm B for Edge-Clique Cover. Then, we have B(H) ≤ √ c ϕ(H). Combining this inequality with Claim 1 yield B(H) ≤ √ c (n+m θ(G)). We now apply the constructive proof of Claim 3 to obtain an approximate A(G) of θ(G). We have

A(G) ≤ B(H) -n -1 m -1 + 7 = B(H) m -1 - n + 1 m -1 + 7 ≤ √ c (n + m θ(G)) m -1 - n + 1 m -1 + 7 ≤ n √ c m -1 + ( √ c ) 2 θ(G) m -1 - n + 1 m -1 + 7 ≤ ( √ c ) 2 θ(G) + n √ c m -1 - n + 1 m -1 + 7 = c θ(G) + O(1).
The constant makes no problem since θ(G) is bound to grow with n since we assume ∆(G) is bounded. ⊓ ⊔

Recognizing graphs with fixed intersection or overlap number

A central algorithmic problem corresponding to an intersection (resp. overlap) graph class G is the so called G-Recognition problem: Given a graph G, is G ∈ G? In this section, we show that this problem is linear-time solvable for graphs with fixed intersection or overlap numbers.

Proposition 3. Let G be any intersection (resp. overlap) graph class, and let k ∈ N.

The G-Recognition problem can be solved in linear-time when restricted to graphs with intersection (resp. overlap) number at most k.

For ease of presentation, we will prove this result for graphs with small intersection numbers. The proof for overlap numbers is along the same lines. The proof of proposition 3 heavily relies on the notion of well quasi orders. A quasi order (i.e., a binary reflexive transitive relation) is a well quasi order (or wqo for short) if it does not contain infinitely descending sequences nor infinite antichains. For example, the standard order ≤ of the natural numbers N is a well quasi order. Another less obvious example is given by considering vectors in N d . For two vectors -→ x ∈ N K 1 and -→ y ∈ N K 2 , let us write -→ x ≤ -→ y if K 1 ≤ K 2 and x i ≤ y i for all i ∈ {1, . . . , K 1 }. The following lemma follows directly from a classical result known in the literature as Higman's Lemma [START_REF] Higman | Ordering by divisibility in abstract algebras[END_REF].

Lemma 1. The set N K is well quasi ordered by ≤ for any fixed K ∈ N.

A characteristic vector of a graph G is a vector -→ c ∈ N K such that there exists According to the above definition, a graph G of dimension K may have several characteristic vectors -→ c ∈ N K . However, all of these must be isomorphic. We say that two characteristic vectors -→ c , -→ d ∈ N K are isomorphic if there is a permutation π ∈ S K such that c i = d π(i) for all i ∈ {1, 2, . . . , K}. It is not difficult to see that two graphs are isomorphic if and only if they both have the same dimension K, and any pair of characteristic vectors of dimensions K for these graphs are isomorphic. The immediately implies the following lemma whose proof is omitted. We next show two applications of Lemma 3. The first application allows us to show that graphs of bounded intersection number are wqo by the induced subgraph order.

Fig. 2 .

 2 Fig. 2. The three edge-gadgets used in the proof of Proposition 1 for vertex u ∈ V(G) with edges eu[0] = {u, v}, eu[1] = {u, w}, and eu[2] = {u, x}.

a partitioning {V 1 , V 2 ,

 12 . . . , V k } of V(G) satisfying the two following properties for each i ∈ {1, 2, . . . , K}: (i) |V i | = c i , and (ii) N [u] = N [v] for all u, v ∈ V i . Define the dimension of a graph G to be the minimum number K such that G has a characteristic vector of dimension K. Lemma 2. A graph G with i(G) ≤ k has dimension at most K = 2 k .Proof. Since i(G) ≤ k, G has a representation F with | F | ≤ k, which implies that there are at most 2 k distinct sets in F. Since vertices of G corresponding to identical sets in F have identical neighborhoods, the lemma follows.⊓ ⊔

Lemma 3 .

 3 A graph H is an induced subgraph of a graph G if and only if H has a characteristic vector -→ c (H) with -→ c (H) ≤ -→ c (G) for some characteristic vector -→ c (G)of G.

 Lemma 4.Let k ∈ N. The set of all graphs G with i(G) ≤ k is wqo by the induced subgraph order.

Proof. Let G denote the set of all finite graphs G with i(G) ≤ k. Clearly there are no infinite descending sequences in G w.r.t. the induced subgraph order, and so to prove the lemma it suffices to show that there are also no infinite antichains in G. Consider a infinite subset of graphs G ′ ⊆ G, and let

⊓ ⊔

We are now ready to give the proof of Proposition 3.

Proof (of proposition 3). Let G any intersection graph class, and let G denote the set of all finite graphs not in G. Also, let H denote the set of all minimal graphs in G w.r.t. the induced subgraph order. That is,

Observe that G is closed under induced subgraphs (i.e., H ∈ G whenever H is an induced subgraph of some graph G ∈ G). This implies that a graph G belongs to G if and only if no graph H ∈ H is an induced subgraph of G. Now by Lemma 4, the set H is finite, and its size depends only on G. Thus our recognition algorithm for G has the set of graphs H "hard-wired" into it, and on given input graph G, it simply checks whether any H ∈ H is an induced subgraph of G, determining that G / ∈ G if and only if any of these checks turns out positive. The running-time of this algorithm is linear by Lemma 5, and since the number and sizes of graphs in H is constant w.r.t. the size of G.

⊓ ⊔


Bijan Mohammadi

Frederic Bouchette

G Éosciences Montpellier

EXTREME SCENARIOS FOR THE EVOLUTION OF A SOFT BED INTERACTING WITH A FLUID USING THE VALUE AT RISK OF THE BED CHARACTERISTICS -------------------------COMPUTERS & FLUIDS, 89 (2014)

Keywords: Value at Risk, uncertainty, shape deformation, shape optimization, beach morphodynamics, Saint Venant Equations, sensitivity analysis, worst-case analysis

We show how to introduce the Value at Risk (VaR) concept in the analysis of the adaptation of the shape of a soft bed to a flow knowing the Probability Density Function (PDF) of the responses of the shape to flow perturbations (bed receptivity). Our aim is to quantify our confidence on simulation scenarios by an available morphodynamic model for the shape. The approach permits to perform this task at low complexity as it does not require any sampling of the bed receptivity parameter space. The paper goes beyond stationarity for the variability of the bed receptivity by linking its dynamics to the bottom morphodynamics through an original transport equation for the local bed receptivity standard deviation. The approach has been applied to the analysis of bed morphodynamics based on minimization principles. The results show the importance of including uncertainty information during the coupling and not only eventually through simple margins on the results.

Introduction

There is an increasing demand to account for data uncertainties in simulation and design. We are interested by situations where a PDE based state equation is involved as typically in a flow problem in a bounded domain. An important situation is where the boundary of the domain, or some part of it (e.g. a shape in a flow), evolves under the action of the flow. Examples of such interactions can be seen in the thermal ablation of a shape or in the changes of a sandy bed of a river or sea. Obviously, these boundary evolutions involve different sorts of materials, flow constituants and physics but share a same global philosophy: they permit to dump or dissipate some energy expression.

Consider the following simulation chain linking a control parameter ρ, its random perturbation ε(ρ) known through a probability density function (PDF) (ρ being then the perturbed control parameter), a state variable u(ρ) and a cost function J: [START_REF] Mandic | Recurrent Neural Networks for Prediction: Architectures, Learning Algorithms and Stability[END_REF] ρ → ρ = ρ + ε(ρ) → u(ρ) → J(u(ρ)).

Without being exhaustive, to handle these perturbations one classical approach is to propagate the randomness into the whole chain and get a noisy functional.

And then assimilate, in a least-square sense for instance, this functional by a lowcomplexity model (e.g. a parametric representation of the functional) and later use this reduced-order model instead of the original one. This approach is widely used in robust engineering optimization and demands for a priori regularity hypothesis for the reduced-order model and trust regions definition. Another possibility is to define the momentum of our noisy functional in momenta-based optimization (e.g. minimizing the mean while keeping the variance unchanged). This is also very much used in practice if the number of control parameters is small and the complexity of each simulation reasonable. These approaches receive different denominations following the field of research they are issued from: learning in neural networks, fitting with least squares in experimental plans or higher degrees polynomials, reduced-order modeling with proper orthogonal decomposition or other low-complexity modeling [START_REF] Mandic | Recurrent Neural Networks for Prediction: Architectures, Learning Algorithms and Stability[END_REF][START_REF] Hoel | Introduction to Mathematical Statistics[END_REF][START_REF] Lindman | Analysis of Variance in Complex Experimental Designs[END_REF][START_REF] Spooner | Stable Adaptive Control and Estimation for Nonlinear Systems: Neural and Fuzzy Approximator Techniques[END_REF][START_REF] Veroy | Certified real-time solution of the parametrized steady incompressible Navier-Stokes equations: Rigorous reduced-basis a posteriori error bounds[END_REF][START_REF] Kapur | Reliability in Engineering Design[END_REF][START_REF] Nocedal | Numerical Optimization[END_REF].

Our motivation is somehow different. Indeed, relation [START_REF] Mandic | Recurrent Neural Networks for Prediction: Architectures, Learning Algorithms and Stability[END_REF] represents an important situation in which where randomness appears is well identified. Indeed, if ε(ρ) = 0 the simulation is fully deterministic. We would like to keep it so and still take into account these random perturbations through extreme scenarios derived by the introduction of a priori information on ε(ρ) into the simulation chain. And, to keep the complexity low, this should be achieved without any sampling of the control space.

Extreme scenarios are interesting in environmental simulations as they provide an easy tool for risk quantification. One application of the present contribution is to permit the derivation of extreme scenarios for the evolution of the shape of soft beds following previous contributions on the application of control theory to the evolution of sandy sea beds [START_REF] Bouharguane | Optimal dynamics of soft shapes in shallow waters[END_REF][START_REF] Bouharguane | Minimization principles for the evolution of a soft sea bed interacting with a shallow sea[END_REF] which are useful, for instance, when designing defense structures against beach erosion [START_REF] Azerad | Optimal shape design of coastal structures minimizing short waves impact[END_REF][START_REF] Azerad | Shape optimization of geotextile tubes for sandy beach protection[END_REF][START_REF] Bouharguane | Low complexity shape optimization and a posteriori high fidelity validation[END_REF]. We model sea bed evolution through fluid and structure coupling. The fundamental assumption in this interaction is that the bed adapts to the flow by some sort of optimal sand transport in order to minimize the flow energy or some other functional. The literature on coastal morphodynamics is huge [START_REF] Dean | Coastal processes with Engineering Applications[END_REF][START_REF] Dean | Water Wave Mechanics for Engineers and Scientists[END_REF][START_REF] Mei | The applied dynamics of ocean surface waves[END_REF][START_REF] Dronkers | Dynamics of Coastal Systems[END_REF][START_REF] Nielsen | Coastal and Estuarine Processes[END_REF] and concerns phenomena with very different time scales, as for instance, sediment transports using fluid-induced shear in the sediment modelling, sea bed friction and the feedback of bed shapes on the flow, dunes morphodynamics, global beach morphodynamics based on long and crossshore fluxes and beach lines morphodynamics. In our model, the time scales of interest are rather small and recoveries between storms or seasonal and inter-annual variabilities are out of scope.

Several quantities can be considered as uncertain in the bed definition (e.g. bed receptivity to flow perturbation) as well as in the flow characteristics (e.g. wave amplitudes, frequencies and directions). In this work we consider variabilities on the bed receptivity (ρ 0) we would like to account for in the evolution of the bed through two extreme scenarios. Each scenario is based on a local threshold value for the bed receptivity defined for a given probability level through VaR ± α∈[0,1[ . Hence, we can give information such as: following our knowledge of the uncertainties on the bed (PDF) and based on the physics encapsulated in the models, there is α × 100% chances for the evolution of the bed to take place between these two scenarios.

We consider Gaussian PDF, but the approach is not limited to those. Gaussian PDFs are interesting as they permit to easily express the VaR from the standard deviation. Usually the variability on an uncertain parameter is assumed stationary.

One originality in this paper is the introduction of a transport equation for the standard deviation following the evolution of the bed. The stationary variance case can then be treated as a particular situation.

The paper starts with the concept of the Value at Risk. Then a model problem is proposed to illustrate the different ingredients in the coupling between a soft shape and a flow based on the minimization of some energy quantity. The variability of the shape characteristics is then accounted for in the minimization and it is shown how to introduce an equation to model the dynamics of this variability following the shape deformation. The approach is made more realistic with the introduction of the Saint Venant flow model for shallow waters. The paper also shows several simulations with quantitative extreme scenarios. The simulations show the importance of including VaR information all along the coupling and not only eventually through security margins as often in engineering approaches. Indeed, we see that the deviations between the simulations are not necessarily correlated with the uncertainty distributions.

Value at Risk (VaR)

In financial engineering, the Value at Risk (VaR) is a widely used risk measure of the risk of loss on a given asset [START_REF] Ph | Value at Risk: The New Benchmark for Managing Financial Risk[END_REF]. It defines, for a given probability level (0 < α < 1) and time horizon (typically one day), a threshold value for the loss X on the asset:

VaR α = inf{l ∈ IR : P (X > l) 1 -α}.
This is illustrated in figure 1 where the areas filled worth α. We would like to use this concept during our simulation knowing the PDF of the uncertainties on the bed receptivity. Hence, during our fluid-structure coupling the bed receptivity ρ represents, with a confidence level of α, the interval [max(0, ρ + VaR - α ), ρ + VaR + α ] around ρ the value one would have used for the bed receptivity in a deterministic simulation and VaR - α 0 VaR + α . One expresses then possible deviations from ρ via two PDF and the corresponding values at risk. One can make the hypothesis that the upper and lower bounds of the variations are symmetric, in which case VaR - α = -VaR + α . This is typically the case when uncertainties on a parameter follow a Gaussian distribution. We will introduce a dynamic model for the variability to address the time issue and the fact that the VaR may also be time dependent. This makes sense as, indeed, when the bed changes its local receptivity might change as well. In this case the stationary situation is treated as a particular case.

In the context of Gaussian probability density functions values at risk are explicitly known: VaR 0.99 = 2.33 and VaR 0.95 = 1.65 for N (0, 1) and VaR α (N (0, σ)) = σVaR α (N (0, 1)). We suppose Gaussian PDF for the bed receptivity ρ and its VaR is therefore known.

The choice for a positive ρ has two reasons. ρ should be linked with the bed porosity (η 0) in bed transport models such as equation [START_REF] Audusse | A fast and stable well-balanced scheme with hydrostatic reconstruction for shallow water flows[END_REF] and we would like to use it in a minimization procedure. In other words, we make the assumption that the bed will take the steps which will decrease the functional (see sections 3 and 4).

A simple illustrative model

Let us illustrate our purpose on a model problem based on an analytical expression for the variations of a surface h. Consider a domain with a bed defined as a function ψ(t, x) : IR + × [-100m, -20m] → IR + . We want to model the changes in this bed with time due to elevations h(t, x). With the notations of the chain (1) u = (ψ, h).

Let us start with the following simple expression for h:

h(t, x) = h 0 + β sin(ωx(h 0 -ψ(t, x))),
where h 0 indicates the level at rest, β and ω are given such that 0 β < 1 and ω > 0. This is a monochromatic wave, but one could consider superimposed waves as in section 6. We consider h 0 = 1.3m, ω = 1Hz and β = 0.1m. The bed is supposed initially flat ψ(0, x) = 1m. To close this model, we need to provide a model for ψ(t, x) and ρ(t, x). We suppose that ψ will adapt to the flow elevation in order to reduce a functional J(h) given by the L 2 norm of h in space:

(2)

J(h) = 1 2h 2 0 -20 -100 h 2 (t, x)dx.
The scaling coefficient is chosen in order for ∇ ψ J to be dimensionless. The choice of the functional is not central in our discussion.

An example of evolution model from time t to time t + δt for this system can be:

(3)

ψ(t + δt, x) = ψ(t, x) -δtρ(t, x)∇ ψ J(ψ(t, x), h(t, x)), h(t, x) = h 0 + β sin(ωx(h 0 -ψ(t + δt, x))).
ρ(t, x)(m/s) 0 models the receptivity of the bed and depends on both time and space as the bed is usually non uniform. If ρ is assumed stationary in time one simply has ρ(t, x) = ρ 0 (x) given. Variability on the bed receptivity can be introduced and accounted for during the simulation through VaR information. For instance, if we assume Gaussian PDF for the bed receptivity with its standard deviation σ(x) known and VaR ± 0.95 (N (0, σ(x))) = ±1.65σ(x). Two scenarios can be considered therefore with ρ 0 (x) + VaR ± 0.95 (N (0, σ(x))). One way to go beyond the stationarity hypothesis for ρ is to consider σ being also a function in time and introduce an extra transport equation for σ(t, x). This is, for instance, useful if the variability changes with the motion of the bed. Let us rewrite the evolution for ψ above as governed by a transport equation: ( 4)

ψ(t + δt, x) = ψ(t, x) -δtρ(t, x)∇ ψ J(ψ(t, x), h(t, x)) = ψ(t, x) -δtV (t, x)∂ x ψ(t, x).
Eq. ( 4) permits to define V (t, x) = ρ(t, x)∇ ψ J/∂ x ψ as the 'equivalent' local speed of the motion of the bed (see figure 2 for snapshots of V ). Now the evolution of local variability can be linked to V by: ( 5)

σ(t + δt, x) = σ(t, x) -δtV (t, x)∂ x σ, σ(t = 0, x) = σ 0 (x).
This transport equation is completed by characteritics boundary conditions following the sign of V at each of the boundaries.

This model suggests that the bed velocity increases when the bed is or gets flat.

In other words, flat beds appear being unstable which is something one observes in nature. Another way to write the dynamic of σ is by the introduction of variable time scales for the bed following its slope (see also section 4):

(6) σ(t + δt, x) = σ(t, x) -δtρ(t, x)∇ ψ J ∂ x σ, σ(t = 0, x) = σ 0 (x),
with δt = δt/∂ x ψ → ∞ when the bed gets flat which suggests one should look for the steady solution of ( 6) in such regions where iso-σ appears parallel to the variation of the shape. In realistic situations, one should not dissociate the sensitivity of the functional with respect to the bed ∇ ψ J from the local bed slope ∂ x ψ. Indeed, we will see in section 4 with the Saint Venant shallow water equations [START_REF] De | Théorie du mouvement non-permanent des eaux, avec application aux crues des rivières et à l'introduction des marèes dans leur lit[END_REF] as state equations that the bed slope is actually accounted for in the state equations and therefore in their linearization leading to ∇ ψ J.

Now let us account for this variability in a numerical simulation. We assume

Gaussian PDF for the bed receptivity with its initial standard deviation increasing linearly through the domain and VaR ± 0.95 (N (0, σ)) = ±1.65 × 10 -3 | x+100 100 | as shown in figure 2. The figure also shows the evolutions of the bottom shapes and water elevations with 70 iterations of ( 3) with δt = 2s on a 500 points mesh when the bed receptivity follows the two extreme scenarios mentioned. The evolution of the bed receptivity variability following ( 5) is also shown in the picture. One can see that in both extreme cases the bottom has adapted in order to reduce surface elevations.

The deviation between the two solutions increases with the variability. Obviously, the elevation reduction is less efficient when the bed receptivity is lower. One will see in section 6 that these informations are not necessary correlated. This approach permits therefore to link data variability to the solution of a model and exhibit solution ranges with a quantifiable statistical theoretical background.

Interactions between the flow and its bed

Now, we consider two dimensional situations with a realistic flow model in shallow domains. The sea bed ψ changes with time following the changes in the state given by the flow variables U. We use a bed parameterization based on the bathymetry given at all the nodes of the fluid mesh.

The model for the sea bed evolution is based on the minimization of a time

dependent functional J(ψ, {U(ψ(τ, x), τ, x), τ ∈ [t -T, t], x = (x 1 , x 2 ) ∈ Ω ⊂ IR 2 })
involving the state evolution in time, solution of a state equation.

We consider the Saint Venant shallow water equations as state equations for the fluid with U = t (h, hu) where u = t (u, v) is the depth-averaged velocity with u and v the scalar components in the horizontal directions and h the local water depth:

∂ t U + F (U, ψ) = 0,
with initial and boundary conditions, where ( 7)

F (U, ψ) =   ∇.(hu) ∇.(hu ⊗ u) + gh∇(h + ψ)   ,
where g(m.s -2 is acceleration due to gravity.

As in our illustrative problem of section 3, J is minimized looking for the evolution in time of ψ following:

(8) ∂ t ψ = -ρ(t, x)∇ ψ J, ψ(t = 0, x) = ψ 0 (x) = given,
where ρ(t, x) is a positive parameter which depends on the local porosity of the bed and quantify its receptivity to flow perturbations. This can also be linked to transport models for the bed such as the Exner equation described in section 4.4.

The physical time scales for the fluid and structure (bed motion) are quite different.

Indeed, flows have time scales of the order of seconds and the sea bed motion takes place over hours as we will see in section 6.

4.1. Cost function . The cost function involves the state evolution as, for instance, in:

(9) J(ψ) = K t t-T j(ψ, U(ψ, τ ))dτ,
where T indicates a time dependency window and also permits to introduce a difference in time scales between sea bed and flow motions. The scaling K is to make ∇ ψ J dimensionless. One looks for the bed acting as a flexible structure and adapting to the flow conditions in order to minimize some energy-based functional. In [START_REF] Bouharguane | Optimal dynamics of soft shapes in shallow waters[END_REF][START_REF] Bouharguane | Minimization principles for the evolution of a soft sea bed interacting with a shallow sea[END_REF] one considers a functional made of the L 2 norm of the deviation of the wave elevation from a low frequency component evaluated using a time interval T :

η(x, t) = h(x, t) -1 T t t-T h(x, τ
)dτ and involving a constraint on sand displacements requiring minimal topobathymetry changes from the bathymetry ψ(t -T ) at the beginning of a time interval of influence [t -T, t]:

(10) J(ψ) = 1 |Ω|T h 0 t t-T Ω η 2 + (ψ(τ ) -ψ(t -T )) 2 dτ dΩ,
where Ω is the observation domain and h 0 is the water level at rest. Alternatively, in this work we give examples of simulations (see section 6) with another functional which aims at minimizing water elevations and their spatial gradients on a given time interval T :

(11) J(ψ) = 1 |Ω|T t t-T Ω |η| ∇ x η dτ dΩ.
4.2. Variability dynamics. Proceeding as in our model problem, we introduce the bed speed and rewrite [START_REF] Dean | Coastal processes with Engineering Applications[END_REF] ρ∇

ψ J = V (t, x)∇ x ψ(t, x) = v 1 ∂ x 1 ψ + v 2 ∂ x 2 ψ,
which permits, after multiplying by ∂ x 1 ψ∂ x 2 ψ, to introduce a transport equation for σ(t, x) characterizing the dynamics of the variability of ρ(t, x):

(13) |∂ x 1 ψ∂ x 2 ψ| ∂ t σ + Sρ∇ ψ J (∂ x 2 ψ∂ x 1 σ + ∂ x 1 ψ∂ x 2 σ) = 0,
with an initial condition σ(t = 0, x) = σ 0 (x) and S = sgn(∂ x 1 ψ∂ x 2 ψ). This transport equation is completed by either symmetry or characteristic boundary conditions (denote n = (n 1 , n 2 ) the local outward normal to the boundary):

∇ x σ.n = 0 or σ(t, x) = given if Sρ∇ ψ J (∂ x 2 ψ n 1 + ∂ x 1 ψ n 2 ) < 0.
This model suggests that the time scale is locally modified following the local geometry of the bed expressed through |∂ x 1 ψ∂ x 2 ψ|. For instance if this quantity vanishes (i.e. the bed is flat in some direction) one should consider stationary solution of [START_REF] Dean | Water Wave Mechanics for Engineers and Scientists[END_REF] (see figure 3 for an example). This is therefore a very stiff equation to solve. Figure 4 shows an example of ρ 0 (x) + σ 0 (x) and ρ(t, x) + σ(t, x).

4.3.

Conservation . If the simulation takes place in a closed domain Ω ′ the amount of the material making the bed must be conserved: ( 14)

Ω ′ ∂ t ψdω = 0 or Ω ′ ψdω = C = constant.
In conservation form the analysis above makes looking for V such that:

(15) ρ∇ ψ J = ∇ x • (ψ(t, x)V (t, x)) = ∂ x 1 (ψv 1 ) + ∂ x 2 (ψv 2 ),
which gives in integral form a constraint on the field V :

Ω ′ ∇ x • (ψV )dω = ∂Ω ′ ψ(V.n)dγ = Ω ′ ρ∇ ψ Jdω = 0. Expressing V = (ρ∇ ψ J/∂ x 1 ψ, ρ∇ ψ J/∂ x 2 ψ
) and n = (n 1 , n 2 ) one has:

Ω ′ ∂ x 1 ( ψρ∇ ψ J ∂ x 1 ψ ) + ∂ x 2 ( ψρ∇ ψ J ∂ x 2 ψ )dω = ∂Ω ′ ψρ∇ ψ J( n 1 ∂ x 1 ψ + n 2 ∂ x 2 ψ )dγ (16) = Ω ′ ρ∇ ψ Jdω = 0.
For ∇ ψ J to be compatible with this constraint on V , the cost function ( 9) must be augmented by a penalty term (e.g. [START_REF] Mei | The applied dynamics of ocean surface waves[END_REF].

| Ω ′ ψdω -C|/|Ω ′ |) enforcing constraint
Let us analyze expression ( 16) supposing ψ > 0 and ρ > 0. The condition on ρ means that the bed is receptive to perturbations everywhere and has no solid parts (ρ = 0). In all cases, it is difficult in practice to enforce a no bed motion just along the boundaries in an experiment with a sandy bed. One way to be sure for the last expression to vanish for all cost functions J is to have

n 1 ∂ x 2 ψ = -n 2 ∂ x 1 ψ
which is difficult to realize. Indeed, consider Ω ′ to be square as in figure 4. The unit normals along the boundaries of this domain are either (±1, 0) or (0, ±1). The only shape for which this condition is surely realized is a flat bed (ψ = cste) which we saw is an unstable shape. So the best way to make sure that the conservation constraint on V is realized is for ∇ ψ J to vanish along the boundaries. This means that the observation domain Ω used in the definition of the cost function should be small compared to the domain Ω ′ . However, for experiences taking place over a long period of time, it is impossible to remove the influences of the boundaries of Ω ′ on what is happening in Ω. This brings therefore the question of the pertinence of extending conclusions on a bed long-term evolution obtained from an experiment in a basin to open seas (see section 6 for an example).

4.4.

Application with the Exner equation. The present analysis of extreme scenarios using the VaR concept can be applied to other models of bed motion available in the literature as, for instance, the Exner equation [START_REF] Paola | A generalized Exner equation for sediment mass balance[END_REF] which models the conservation of mass between 'in the bed' and 'transported' sediments:

(17)

ψ t = - 1 1 -λ p (t, x) ∇.q, ψ(t = 0, x) = given,
where λ p ∈ [0, 1[ is the porosity of the bed or void fraction (i.e. a fraction of the volume of voids over the total volume). This coefficient plays the role of ρ in the minimization equation ( 8): bed receptivity increases with λ p . q is a function of the flow variables. In [START_REF] Bouharguane | Optimal dynamics of soft shapes in shallow waters[END_REF][START_REF] Bouharguane | Minimization principles for the evolution of a soft sea bed interacting with a shallow sea[END_REF] one shows that equation ( 8) is a particular Exner equation with a non local flux similar to one in a model given by Fowler [START_REF] Fowler | Dunes and drumlins[END_REF]. At this point, if the PDF of the variability in λ p is known, it can be accounted for, in the same way than for ρ, through its VaR. This permits using a solution solver for the Exner equation to generate extreme scenarios of bed evolution.

Sensitivity evaluation

Sensitivity evaluation in large dimension needs an adjoint variable approach to make the cost of the evaluation independent from the size of the control space. In time dependent problems, this implies storage of all intermediate states which can be optimized by check-pointing technics [START_REF] Griewank | Computational derivatives[END_REF][START_REF] Hascoet | Tapenade 2.1 user's guide[END_REF]. In this section, we briefly describe the adjoint method with a time dependent state equation (the Saint Venant equations in our case).

Let us consider the following formal dependency chain:

ψ → {U(ψ, τ ), τ ∈ [0, T ]} → J(ψ, T ).
Here, ψ is the independent variable and U and J are the dependent ones. U(ψ, τ ) are solutions in time of ( 18)

∂ t U + F (U, ψ) = 0, U(0) = U 0 (ψ).
To be accurate, one should have also to consider the independent physical parameters such as those describing the waves. But, this would have introduced unnecessary complications into notations. Now consider a functional involving an integral over time like those we are interested in:

J(ψ, T ) = (0,T ) j(ψ, U(ψ, t)).
Linearizing J one has:

J ψ (ψ, T ) = (0,T ) (j ψ + j U U ψ ).
In this expression only U ψ is costly to get as it requires the linearization of the shallow water equations.

The linearized state equation:

(19) ∂ t (U ψ ) + F ψ (U, ψ) + F U (U, ψ)U ψ = 0, U ψ (0) = U ′ 0 (ψ),
permits to write for all function V (where V has the same structure than U):

0 = (0,T )×Ω (∂ t (U ψ ) + F ψ (U, ψ) + F U (U, ψ)U ψ ) V.
Introducing the adjoint operator F * U , it gives:

0 = (0,T )×Ω (-∂ t V + F * U (U, ψ) V)U ψ + Ω [VU ψ ] T 0 + (0,T )×Ω VF ψ (U, ψ).
Let us introduce a backward adjoint problem:

(20)

∂ t V + F * U (U, ψ) = j U , V(T ) = 0.
Therefore, with V solution of the backward adjoint equation [START_REF] Paola | A generalized Exner equation for sediment mass balance[END_REF] with the chosen final condition one has:

(0,T )×Ω j U U ψ = Ω V(0)U ′ 0 (ψ) - (0,T )×Ω VF ψ (U, ψ).
If there is no direct dependency between the initial condition U(0) and ψ the first term in the right-hand-side vanishes. Also, for the Saint Venant equations the direct dependency in ψ is in gh∇ψ in the equations for hu, see [START_REF] Mohammadi | Applied Shape Optimization for Fluids[END_REF].

Denoting V = (v 1 , v 2 ) t
with v 2 the adjoint variable associated to u, one has in weak form:

(0,T )×Ω VF ψ (U, ψ) = - (0,T )×Ω g∇.(hv 2 ).
We have used either slip or Dirichlet boundary conditions for the velocity which give for the corresponding adjoint variable slip or homogeneous Dirichlet conditions removing the boundary term in weak form. An important point here is that, unlike with the linearized equation, with ψ of any dimension V is computed only once. One remarks however that states U are needed in reverse order because the backward integration in [START_REF] Paola | A generalized Exner equation for sediment mass balance[END_REF].

The previous analysis has been implemented by automatic differentiation [START_REF] Hascoet | Tapenade 2.1 user's guide[END_REF][START_REF] Mohammadi | Applied Shape Optimization for Fluids[END_REF][START_REF] Mohammadi | Shape Optimization in Fluid Mechanics[END_REF] applied to a solver for the shallow water equations. In this code the equations are discretized by a finite volume formulation. Our finite volume implementation preserves steady state solutions on non flat sea beds in the absence of perturbations [START_REF] Audusse | A fast and stable well-balanced scheme with hydrostatic reconstruction for shallow water flows[END_REF][START_REF] Audusse | A well-balanced positivity preserving second order scheme for shallow water flows on unstructured meshes[END_REF]. Four boundary conditions are needed at slip, inlet, shoreline and outlet the bed models in one period as the flow time step is around 0.005s which gives a coupling time scale T of 0.5s. Details on the solver are given in [START_REF] Bouharguane | Optimal dynamics of soft shapes in shallow waters[END_REF]. As this is not central in the paper we avoid extensive details on the solution procedures for the Saint Venant equations.

Examples of shape adaptations following VaR-based extreme scenarios

We consider a flat soft bed interacting with a flow governed by the shallow water equations. The way the bed responds to flow perturbations is defined in section 4. We would like to show the impact of the variability in the bed receptivity ρ for which we assume Gaussian PDF around a constant value of 0.002m/s with VaR ± 0.95 (N (0, σ)) = ±f (x) linearly increasing cross-shore as in our simple model of section 3 and shown in figure 2.

The initial bed is flat and waves are produced on the left boundary of the domain Ω representing a square wave basin de side 30 m. To simulate sea conditions, the water wave elevation at the inlet is represented by the addition of N monochromatic waves:

h(t) = h 0 + 2A i=1,..,N -1 sin ω i + ω i+1 2 t cos ω i -ω i+1 2 t .
A = 0.12m is the water wave amplitude at inlet, h 0 = 0.765 m the water height at rest and ω i = 2π/T i are wave pulses. With two modes, typical values of periods T i we consider are 3.5s and 2.5s. More realistic conditions can be applied following a

Jonswap distribution [START_REF] Hasselman | Measurements of Wind-Wave Growth and Swell Decay during the Joint North Sea Project (JONSWAP)[END_REF][START_REF] Hasselmann | Directional Wave Spectra Observed during JONSWAP 1973[END_REF].

As specified in section 4.1, the functional we consider for this coupling aims at minimizing water elevations and their spatial gradients on a given time interval T = 0.5s. Figure 5 shows two scenarios for the bed after 400 minutes of interaction with the flow minimizing [START_REF] Bouharguane | Low complexity shape optimization and a posteriori high fidelity validation[END_REF]. The scenarios differ in the bed receptivity levels (ρ = 0.0002m/s and ρ = 0.002m/s). Three-dimensional structures appear in the higher receptivity case (with light sand) despite that the incoming wave is mono-directional.

These disappear when the bed is made of materials with lower receptivity (with more heavy sand). The longshore variability of the bed shows the ratio between the large longshore structures and these 3D smaller ones. One sees that the global bed organization is faster in the high receptivity situation but there are small fluctuations in the time history of the functional corresponding to the oscillations of the small structures. These are better shown in the enlargement of the time history in figure 6. These oscillations do not exist in the heavy sand configuration. The reduction in the functional is visible comparing these histories to the evolution of the functional on a flat bed not adapting to the flow.

In the sequel, one only considers the higher receptivity setup (i.e. lighter sand with ρ = 0.002m/s) and aims at discussing the variability issues analysis by the ingredients presented in the paper. Figure 6 shows the evolution of the local variability defined by σ(t, x) and its evolution by equation [START_REF] Dean | Water Wave Mechanics for Engineers and Scientists[END_REF]. It also shows the time histories of the functional [START_REF] Bouharguane | Low complexity shape optimization and a posteriori high fidelity validation[END_REF] without the variability accounted for and for the two extreme scenarios defined by VaR ± 0.95 (N (0, σ(t, x))). Figure 7 shows the differences between the two final shapes and bed receptivity variabilities for the two extreme scenarios based on VaR ± 0.95 (N (0, σ(t, x))). σ(t, x) is governed by equation [START_REF] Dean | Water Wave Mechanics for Engineers and Scientists[END_REF]. One sees the importance of accounting for the uncertainty in the simulation and not only at the end through simple security margins as there is not necessary a simple spatial correlation between the shapes deviation and the spatial distribution of the uncertainty in the bed receptivity. Surprisingly, and unlike in the illustrative model problem of section 3, larger deviations between the two shapes do not take place where the bed receptivity features larger variability.

Figure 8 shows a snapshot of the bed velocity V = (ρ∇ ψ /∂ x 1 ψ, ρ∇ ψ /∂ x 2 ψ). This field is evaluated by a postprocessing step from equation [START_REF] Dean | Coastal processes with Engineering Applications[END_REF] and is never used in any calculation. The figure also shows the evolution in time of V L 2 (Ω) . The shape never rests and continues to vary in time around structures organized in two different regions (x 20 and x > 20). The shape is flat in average in the region

x > 20 as shown in figure 5. total sand volume over the domain. This is quite counter intuitive as one would have not expected such an impact from the variability on the bed receptivity. In addition, the total sand volume increases with the scenario using VaR - 0.95 (N (0, σ(t, x))) and decreases with VaR + 0.95 (N (0, σ(t, x))). This approach is therefore also useful to analyze the pertinence of an experimental setup.

CONCLUDING REMARKS

The Value at Risk concept has been introduced to define extreme scenarios for the motion of a soft bed under the action of a flow described by the Saint Venant shallow water equations. The approach, which enters the domain of shape optimization for unsteady fluids with one application being worst-case analysis in coastal erosion, is generic and applicable with other flow or bottom models. It permits to quantify our confidence on the bed evolution without any sampling of the bed characteristics parameter space, and one remains in the deterministic framework with supposed sufficient regularity where the gradient of the functionals can be defined. To go beyond the stationary case for the variance, the bed motion and its local variability Middle-left: reduction of the wave energy in time due to bed motion for the two extreme scenarios given by VaR ± 0.95 (N (0, σ)). Middle-right: VaR based bounds for the bed receptivity and their evolution following 5. Lower: snapshots of V (t, x) = ρ(t, x)∇ ψ J/∂ x ψ the 'equivalent' speed of the motion of the bed during the coupling between the bed and elevation models (3). . Top left: deviation between the two final shapes reached accounting for the two extreme scenarios for the bed receptivity. Top right: deviation between σ ± corresponding to the two extreme scenarios defined by VaR ± 0.95 (N (0, σ(t, x))). Lower pictures is the longshore variabilities of these showing that larger deviations do not necessarily appear where variability in bed receptivity is large. Figure 9. Top left: deviation between the two final shapes reached for the extreme scenarios by VaR + 0.95 (N (0, σ(t, x))) with and without the conservation constraint enforced and on the top right the deviation between the corresponding σ + (same in bottom left and right but with VaR - 0.95 (N (0, σ(t, x)))). Middle picture is the evolution in time of the normalized conservation constraint for these four scenarios.

  boundaries. The slip boundary condition (u.n = 0) is naturally taken into account in a finite volume formulation. The outlet condition is a transmissive boundary condition. Values at boundary cells are obtained by second order extrapolations normal to the boundary from the values inside the domain. To describe incoming waves we use an absorbing/generating inlet boundary condition where the values of water depth are prescribed. In subcritical regimes, characteristic curves and Riemann invariants provide normal velocity. In open sea we allow for reflected waves to freely exit the domain [19]. Time integration is explicit for the flow. Due to what we said on the difference of time scales between fluid motion and changes in sea beds, several time steps will be taken (typically 100) in the flow solver before a new time step by the bed model described by the minimization iterations. In the examples in section 6 where flow comes from superposition of waves with a smallest period of 2.5s, 100 flow iterations imply at least 5 interactions between the fluid and

Figure 9

 9 Figure 9 illustrates the impact of the conservation constraint discussed in section 4.3 on the two extreme scenarios shown in figures 6 and 7. One sees that, as the simulation time is long, one should pay attention to the fact that a closed basin is necessary different than an open sea domain. The deviation between the two beds increases with time. It is interesting that in the absence of the conservation constraint (i.e. open sea condition) the two scenarios predict opposite behaviors for the

Figure 2 .

 2 Figure2. Upper: surface elevation h and bed ψ evolutions for the illustrative problem of section 3 subject to bed receptivity variability. Middle-left: reduction of the wave energy in time due to bed motion for the two extreme scenarios given by VaR ± 0.95 (N (0, σ)). Middle-right: VaR based bounds for the bed receptivity and their evolution following 5. Lower: snapshots of V (t, x) = ρ(t, x)∇ ψ J/∂ x ψ the 'equivalent' speed of the motion of the bed during the coupling between the bed and elevation models (3).

Figure 3 .

 3 Figure 3. Example of bed ψ and the inverse of the local time scale (right) in the solution of[START_REF] Dean | Water Wave Mechanics for Engineers and Scientists[END_REF]. When this vanishes, one should look for steady solutions making the problem stiff.

Figure 4 .Figure 5 .

 45 Figure 4. Example of a locally perturbed initial constant bed receptivity (left) and its dispersion governed by equation (13) (right).

Figure 6 .

 6 Figure 6. σ ± corresponding to the two extreme scenarios defined by VaR ± 0.95 (N (0, σ(t, x))). σ ± initialisation are linear cross-shore through the domain as shown and their dispersions governed by equation (13). Lower picture is the time histories of the functional (11) without variability and with two VaR-based scenarios for the local bed receptivity ρ(x, t).

Figure 7

 7 Figure 7. Top left: deviation between the two final shapes reached accounting for the two extreme scenarios for the bed receptivity. Top right: deviation between σ ± corresponding to the two extreme scenarios defined by VaR ± 0.95 (N (0, σ(t, x))). Lower pictures is the longshore variabilities of these showing that larger deviations do not necessarily appear where variability in bed receptivity is large.

Figure 8 .

 8 Figure 8. Snapshots of V at three different stages as indicated and the time histories of the L 2 norm of V for the two extreme scenarios defined by VaR ± 0.95 (N (0, σ(t, x))). The outcome is not intuive as the fluctuations in the simulation with the lower bound VaR - 0.95 in variability remain larger than with VaR + 0.95 .

Acknowledgments: The adjoint Saint Venant solver has been obtained using Tapenade AD tool developed at INRIA-Sophia Antipolis by L. Hascoet and his team Tropics.