David Coudert

Guillaume Ducoffe

Recognition of C 4 -free and 1/2-hyperbolic graphs *

Keywords: Hyperbolicity, discrete metric space, graph algorithms, C4-free graphs, rectangular matrix multiplication

The shortest-path metric d of a connected graph G is 1/2-hyperbolic if, and only if, it satisfies d(u, v)

We show that the problem of deciding whether an unweighted graph is 1/2-hyperbolic is subcubic equivalent to the problem of determining whether there is a chordless cycle of length 4 in a graph. An improved algorithm is also given for both problems, taking advantage of fast rectangular matrix multiplication. In the worst case it runs in O(n 3.26 )-time.

Introduction

The primary aim of our work is to study hyperbolicity of simple unweighted graphs. This is a metric parameter, that was first introduced by Gromov in the context of automatic groups (see [START_REF] Gromov | Hyperbolic groups[END_REF]), then extended to more general metric spaces [START_REF] Bermudo | Gromov hyperbolic graphs[END_REF]. Roughly, the hyperbolicity of a connected graph is a measure of how far is the shortest-path metric of the graph from a tree metric. One can deduce from this parameter tight bounds for the (worst) additive distortion of the distances in the graph when its vertices are embedded into a weighted tree [START_REF] Chepoi | A note on distance approximating trees in graphs[END_REF]. Practical applications of hyperbolicity were proposed in the domains of routing [START_REF] Boguñá | Sustaining the Internet with hyperbolic mapping[END_REF], network security [START_REF] Jonckheere | A hyperbolic geometric approach to multipath routing[END_REF], bioinformatics [START_REF] Dress | Basic Phylogenetic Combinatorics[END_REF], and in the spread of information in social networks [START_REF] Baras | Hyperbolic embedding to the rescue in communication and social networks[END_REF].

So far, the best known algorithm for determining the hyperbolicity of a graph has an O(n 3.69 )-time complexity [START_REF] Fournier | Computing the gromov hyperbolicity of a discrete metric space[END_REF]. This is however prohibitive for graphs with tens of thousands of nodes such as the graph of the Autonomous Systems of the Internet, road maps, etc. An algorithm with good practical performances has been proposed in [START_REF] Cohen | Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs[END_REF]. It improves the worst-case running time on certain graph classes, but it cannot be used on graphs with hyperbolicity less than one.

Related work

Our work focuses on a decision version of the problem, namely the recognition of graphs with hyperbolicity (at most) 1/2. Graphs with small hyperbolicity value have already received some attention, as a first characterization of 1/2-hyperbolic graphs was proposed in [START_REF] Bandelt | 1-hyperbolic graphs[END_REF]. However, to the best of our knowledge, there was no known algorithmic application to it prior to this work. We are more interested in a reduction such as the recent one in [START_REF] Fournier | Computing the gromov hyperbolicity of a discrete metric space[END_REF], where the authors proved an equivalence between the problems of finding a 2-approximation for the hyperbolicity and the (max, min)-matrix multiplication. A recent work [START_REF] Duan | Approximation algorithms for the gromov hyperbolicity of discrete metric spaces[END_REF] further exploits the relation between both problems, yielding constantfactor approximations for the hyperbolicity in subcubic-time. We point out that a similar line of research was followed in [START_REF] Roditty | Minimum weight cycles and triangles: Equivalences and algorithms[END_REF][START_REF] Vassilevska Williams | Subcubic equivalences between path, matrix and triangle problems[END_REF], where they determined the subcubic equivalence between various combinatorial problems.

Our contribution We relate the recognition of graphs with hyperbolicity (at most) 1/2 to the search of (induced) cycles of length 4, e.g. C 4 , in a graph. It actually follows from our work that either both problems are solvable in subcubic-time, or none of them is. We first present a linear-time reduction from the C 4 -free graph recognition problem to the recognition of 1/2-hyperbolic graphs ( §3.1). Then we prove a new characterization of 1/2-hyperbolic graphs, which is based on graph powers [START_REF] Laskar | On powers and centers of chordal graphs[END_REF], and from which it follows that, conversely, deciding whether a graph is 1/2-hyperbolic can be reduced in subcubic-time to the C 4 -free graph recognition problem ( §3.2). In §4, we finally reduce both problems to the problem of the rectangular matrix product that was defined in [START_REF] Franc | Faster algorithms for rectangular matrix multiplication[END_REF]. This allows us to solve both of them in O(n 3.26 )-time, which beats the previous records established in [START_REF] Fournier | Computing the gromov hyperbolicity of a discrete metric space[END_REF][START_REF] Spinrad | Finding large holes[END_REF].

We give the notations used in this paper in §2, along with definitions for graph hyperbolicity and C 4 -free graphs.

Definitions and Notations

A graph G is a pair (V, E), whose n vertices are the elements of the set V , and whose m edges are the elements of E; every edge is a set of two distinct vertices of G. The neighborhood N (u) of a vertex u ∈ V , is the (possibly empty) set of vertices v ∈ V such that {u, v} is an edge. Alternatively, we say that the elements of N (u) are adjacent to u. A clique is a set of pairwise adjacent vertices. Note that the adjacency relation is clearly symmetric; we also define the (symmetric) adjacency matrix A = (I {u∈N (v)} ) u,v∈V , where I denotes the Kronecker delta 1 .

Finally, an

induced subgraph of G is a graph G[X] = (X, F ) such that X ⊆ V and F = {{u, v} ∈ E : u, v ∈ X}.
In particular if X is a clique, then it is called a complete subgraph. The induced subgraph is a path of length l ≥ 0 if |X| = l + 1 and the vertices of X can be linearly ordered into a sequence (v 0 , v 1 , . . . , v l ) such that for every 0 ≤ i, j ≤ l, the vertex v i is adjacent to v j if, and only if, |j -i| = 1. In such a case, the vertices v 0 and v l are called the endpoints of the path, and the path is a v 0 v l -path. The graph G is connected if, for every pair u, v ∈ V , there exists a uv-path. Also, a cycle is a graph such that the deletion of any edge {v 0 , v l } ∈ F yields a v 0 v l -path, and a tree is a connected graph which does not contain any cycle as a subgraph.

Further standard graph terminology can be found in [START_REF] Bondy | Graph theory with applications[END_REF][START_REF] Diestel | Graph theory[END_REF].

1/2-hyperbolic graphs

Given a connected graph G = (V, E), we define the distance d G (u, v) between two vertices u, v ∈ V as the minimum length of a uv-path in the graph. This yields a (discrete) metric space (V, d G ). For a survey of metric graph theory, the reader may refer to [START_REF]Metric graph theory and geometry: a survey[END_REF]. We define in the space (V, d G ) an interval [u, v] between any two vertices u, v ∈ V , as the set of vertices "in between" u and v, e.g.

[u, v] = {x ∈ V : d G (u, v) = d G (u, x) + d G (x, v)}.
In the sequel, we will call a uv-path of minimum length a uv-shortest path, and we will denote the distance function by d instead of d G whenever G is clear from the context. The graph hyperbolicity of G can now be defined as follows:

Definition 1 (4-points Condition, [START_REF] Gromov | Hyperbolic groups[END_REF]). Let G be a connected graph. For every 4-tuple u, x, v, y of G, we define δ(u, v, x, y) as half of the difference between the two largest sums amongst

S 1 = d(u, v) + d(x, y), S 2 = d(u, x) + d(v, y), and
S 3 = d(u, y) + d(v, x).
The graph hyperbolicity, denoted by δ(G), is equal to max u,x,v,y δ(u, v, x, y). Moreover, we say that G is δ-hyperbolic, for every δ ≥ δ(G).

Unlike many well-known graph properties, it is very important to note that the hyperbolicity of an induced subgraph of G does not yield any information in general about the hyperbolicity of G. For example, the wheel W n is 1-hyperbolic, whereas it contains as an induced subgraph the cycle C n whose hyperbolicity grows linearly with n [START_REF] Cohen | Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs[END_REF]. A way to deal with this difficulty is to constrain ourselves to distance-preserving, or isometric subgraphs. Formally, an induced subgraph H of G is isometric if, and only if, it is connected and for every pair of vertices u, v ∈ H, we have that d H (u, v) = d G (u, v). We also say that a subgraph which is not isometric is a bridged subgraph.

Lower and upper bounds on the hyperbolicity can be deduced from classical parameters such as the girth [START_REF] Michel | Hyperbolicity and parameters of graphs[END_REF], the circumference [START_REF] Carballosa | Gromov hyperbolicity of line graphs[END_REF], the domination number [START_REF] Rodríguez | Bounds on Gromov hyperbolicity constant in graphs[END_REF], and the chordality [START_REF] Kosowski | k-chordal graphs: From cops and robber to compact routing via treewidth[END_REF][START_REF] Wu | Hyperbolicity and chordality of a graph[END_REF]. In particular, we have that δ(G) ≤ ⌊diam(G)/2⌋, where diam(G) = max u,v∈V d G (u, v) is the diameter of the graph [START_REF] Cohen | Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs[END_REF][START_REF] Wu | Hyperbolicity and chordality of a graph[END_REF].

We inform the reader that Definition 1 is not a universal definition for the hyperbolicity of a graph. Some authors actually proposed and studied other definitions (see, for instance [START_REF] De | Sur les groupes hyperboliques d'après Mikhael Gromov[END_REF][START_REF] Gromov | Hyperbolic groups[END_REF]). Though the value of δ(G) may vary depending on the choice of the definition, any δ-hyperbolic graph with respect to (w.r.t.) any of the definitions is f (δ)-hyperbolic w.r.t. any other definition of the hyperbolicity. The function f is linear in δ in most cases. Moreover, the class of trees is always contained into the class of 0-hyperbolic graphs, which makes the graph hyperbolicity a tree-likeness parameter.

We here restrict our study to Definition 1, as it has algorithmic applications. Indeed, it is straightforward by using Definition 1 to compute the graph hyperbolicity δ(G) in Θ(n 4 )-time (see [START_REF] Cohen | Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs[END_REF] and [START_REF] Fournier | Computing the gromov hyperbolicity of a discrete metric space[END_REF] for practical and theoretical improvements of the complexity). Also, note that δ(G) is always a half-integer (w.r.t. Definition 1). Our work focuses on graphs with small hyperbolicity, that is hyperbolicity at most 1/2. Those graphs thus satisfy either δ(G) = 0 or δ(G) = 1/2. We address the problem of recognizing those graphs, that we formulate as follows.

Problem 2. Given a connected graph G, is G a 1/2-hyperbolic graph ?

In [START_REF] Bandelt | 1-hyperbolic graphs[END_REF], Bandelt and Chepoi characterized the 1/2-hyperbolic graphs as the connected graphs that simultaneously satisfy the three following conditions:

Condition 3. Every cycle of length at least 6 in G is bridged. Condition 4. For every pair u, v ∈ G, N (u) ∩ [u, v] is a clique. Condition 5. No graph in Figure 1 is an isometric subgraph of G.
A simpler characterization was previously given for 0-hyperbolic graphs [START_REF] Bandelt | Distance-hereditary graphs[END_REF][START_REF] Howorka | On metric properties of certain clique graphs[END_REF]. In fact, 0-hyperbolic graphs are block-graphs, that are graphs in which every biconnected component (block) is a clique (possibly reduced to a single vertex). This class includes cliques and trees, and a block-graph can be recognized in O(n + m)-time.

C 4 -free graphs

The C 4 -free graph recognition problem asks whether a given graph G contains an induced cycle of length 4. In the sequel, such a cycle, if any, is called a C 4 , or a quadrangle. A graph G which does not contain any C 4 as an induced subgraph is a C 4 -free graph. Let us define our decision problem in the following way. Problem 6. Given a graph G, does G contain a C 4 as an induced subgraph ?

We now remind a well-known, local characterization of those graphs:

Fact 7. A graph G = (V, E) is C 4 -free if,
and only if, for every pair of non-adjacent vertices u, v, the set N (u) ∩ N (v) is a (possibly empty) clique.

To see the relation between Problem 6 and Problem 2, one can observe that the condition of Fact 7 is equivalent to Condition 4 when considering vertices u, v at distance 2. As a consequence, every 1/2hyperbolic graph is also C 4 -free. In fact, a more direct way to see this is to note that every induced subgraph which is a quadrangle is isometric (this comes from the fact that a C 4 is connected and it has diameter 2). Since one can easily check that δ(C 4 ) = 1, then it indeed follows that a 1/2-hyperbolic graph cannot contain a quadrangle as an induced subgraph.

So far, the best-known algorithm we are aware of to detect an induced C 4 in a graph has O(n ω(1)+1 ) = O(n 3.3727 )-time complexity [START_REF] Spinrad | Finding large holes[END_REF], with O(n ω (1) ) being the complexity of multiplying two n × n matrices (see §4.1 for details). We will improve this result in §4.

The subcubic equivalence

It is straightforward by the definitions that both the 1/2-hyperbolic graph recognition problem (Problem 2), and the C 4 -free graph recognition problem (Problem 6), are polynomial-time solvable [START_REF] Fournier | Computing the gromov hyperbolicity of a discrete metric space[END_REF][START_REF] Spinrad | Finding large holes[END_REF]. On the other hand, the best-known upper-bound on their time complexity is strictly more than cubic. Thus it motivates the search for subcubic reductions between these problems, as they are defined in [START_REF] Vassilevska Williams | Subcubic equivalences between path, matrix and triangle problems[END_REF]. Formally, a subcubic reduction from a problem A to a problem B is a subcubic-time Turing reduction, which verifies the following additional properties on the oracle access to problem B. For every positive real µ, there has to exist a positive real ε such that:

1. the reduction runs in Õ(n 3-ε )-time 2 , where n denotes the size of the input; 2. and given an instance of size n of problem A, i Õ(n 3-µ i ) = Õ(n 3-ε ), where n i denotes the size of the i th oracle call to problem B in the reduction.

In particular, a linear-time reduction is a subcubic reduction. More generally, any subcubic-time reduction which satisfies i n i = Õ(n) is also a subcubic reduction. We will only consider subcubic reductions of this kind in the sequel. Subcubic reductions are of specific interest in the study of subcubic-time algorithms, because if there exists a subcubic reduction from problem A to problem B, and there is a subcubic-time algorithm which solves problem B, then there also exists a subcubic-time algorithm which solves problem A. In particular, if problems A and B are subcubic equivalent, then either both of them are solvable in subcubic-time, or none of them is. In this section, we will show that Problem 2 and Problem 6 are subcubic equivalent. We first present a linear-time reduction from Problem 6 to Problem 2 in §3.1 (Proposition 8). Then we present a subcubic reduction from Problem 2 to Problem 6 in §3.2 (Theorem 20). Proof. Let G = (V, E) be an instance of the C 4 -free graph recognition problem. Let u / ∈ V , and let

G ′ = (V ∪ {u}, E ∪ {{u, v} : v ∈ V }).
By construction, G ′ is connected, and it has diameter at most 2. Thus, we have that δ(G ′ ) ≤ 1 (e.g. see [START_REF] Cohen | Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs[END_REF]), and all of its isometric subgraphs also have diameter at most 2. Moreover we remind that a cycle of length l has diameter ⌊l/2⌋. In particular, every cycle of length at least 6 is a graph of diameter at least 3 and as such, it cannot be an isometric cycle of G ′ . Consequently, G ′ always satisfies Condition 3. We can prove that it always satisfies Condition 5 in the same way. Finally, since Condition 4 is satisfied for every pair u, v ∈ V of adjacent vertices, then G ′ satisfies Condition 4 if, and only if, for every pair u, v ∈ V of non-adjacent vertices, we have that

N G ′ (u) ∩ [u, v] is a clique; since d G ′ (u, v) = 2 in such a case, then it is equivalent to have that N G ′ (u) ∩ N G ′ (v) is a clique, e.g. the graph G ′ is C 4 -
free by Fact 7. Furthermore, we have by construction that any induced C 4 in G ′ is an induced quadrangle in G, and vice-versa. Consequently, G is C 4 -free if, and only if, the graph G ′ is 1/2-hyperbolic.

We want to highlight that our reduction from Problem 6 to Problem 2 here is linear-time, whereas the converse reduction from Problem 2 to Problem 6, presented in §3.2, is super-linear. It might be of interest to determine whether a linear-time reduction from Problem 2 to Problem 6 exists.

Finding quadrangles to recognize non-1/2-hyperbolic graphs

Our aim is now to prove that there exists a subcubic reduction from Problem 2 to Problem 6 (Theorem 20). Ideally, we would ask for a subcubic-time routine for checking whether Conditions 3, 4 and 5 are satisfied. Our reduction is however more complex, as we actually introduce and verify different conditions in subsequent sections. Thus we have to prove that these conditions imply Conditions 3, 4 and 5, and also that they are satisfied by 1/2-hyperbolic graphs.

Quickly excluding long isometric cycles

Let us first deal for our reduction with a tool that we will use later to verify whether Condition 3 is satisfied. We recall that Condition 3 requires that every cycle of length at least 6 in G is a bridged subgraph. A first naive approach to deal with this condition is to compute the length of a longest isometric cycle of G. This can be done in polynomial-time, but the best-known algorithm runs in O(n 2ω (1) log n) = O(n 4.752 log n)-time, which is super-cubic [START_REF] Lokshtanov | Finding the longest isometric cycle in a graph[END_REF]. Instead, we propose in this section a way to weaken Condition 3, by only having to consider isometric cycles of polylogarithmically-bounded length.

Given a connected graph G, we recall that a c-factor approximation of the hyperbolicity of G is a halfinteger δ c (G) such that δ(G) ≤ δ c (G) ≤ c.δ(G). In this section, we will assume we have a subcubic-time algorithm computing a c-factor approximation of the hyperbolicity, for some fixed choice of c = log O(1) n. Below, we remind possible ways to achieve such a result: Lemma 9 ( [9, [START_REF] Duan | Approximation algorithms for the gromov hyperbolicity of discrete metric spaces[END_REF][START_REF] Fournier | Computing the gromov hyperbolicity of a discrete metric space[END_REF]). Let G = (V, E) be a connected graph.

1. There exists an algorithm computing a 2-factor approximation of the hyperbolicity in O(n3-ω(1)/2 ) = O(n 2.69 )-time [START_REF] Fournier | Computing the gromov hyperbolicity of a discrete metric space[END_REF].

2. For every ε > 0, there exists an algorithm computing a (2 + ε)-factor approximation of the hyperbolicity in Õ(ε -1 n ω(1) ) = Õ(ε -1 n 2.3727 )-time [START_REF] Duan | Approximation algorithms for the gromov hyperbolicity of discrete metric spaces[END_REF].

3. There exists an algorithm computing a 1569-factor approximation of the hyperbolicity in time 3 O(min{nm, n ω(1) log n} + n 2 ) = Õ(n 2.3727 ) [START_REF] Chalopin | Cop and robber game and hyperbolicity[END_REF].

Combining results from [START_REF] Chepoi | A note on distance approximating trees in graphs[END_REF][START_REF] Dor | All-pairs almost shortest paths[END_REF][START_REF] Fournier | Computing the gromov hyperbolicity of a discrete metric space[END_REF], there also exists a θ(log n)-factor approximation algorithm of the hyperbolicity in Õ(n 2 )-time 4 . In addition, one can deduce from the results from [START_REF] Dragan | Tree-like structures in graphs: A metric point of view[END_REF][START_REF] Dragan | An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs[END_REF][START_REF] Gavoille | Distance labeling in graphs[END_REF] an algorithm which computes a θ(log 2 n)-factor approximation of the hyperbolicity in O(m log n)-time.

It is well-known that the hyperbolicity of the cycle C n grows linearly with n. Formally: Lemma 10 ( [START_REF] Cohen | Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs[END_REF][START_REF] Wu | Hyperbolicity and chordality of a graph[END_REF]). Cycles of order 4p + ε ≥ 3, with p ≥ 0 and ε ∈ {0, 1, 2, 3}, are (p -1/2)-hyperbolic when ε = 1, and p-hyperbolic otherwise.

As a result, it follows from Lemma 10 that a (polylogarithmic) upper-bound on the hyperbolicity of G yields a (polylogarithmic) upper-bound on the length of a longest isometric cycle of G; more accurately: Corollary 11. Let G = (V, E) be a connected graph. Then all the isometric cycles of G have length upper-bounded by 4δ(G) + 3.

Proof. First assume δ(G) is an integer. By Lemma 10, the longest δ(G)-hyperbolic cycle has length at most 4δ(G) + 3. Otherwise, δ(G) is a half-integer by Definition 1 and so, again by Lemma 10, the longest δ(G)-hyperbolic cycle has length at most 4(δ(G) + 1/2) + 1 = 4δ(G) + 3.

Since we are interested in 1/2-hyperbolic graphs, then Corollary 11 implies that every isometric cycle must have length upper-bounded by 5 i.e., Condition 3. We introduce in the next section a second tool so that we can detect isometric cycles of polylogarithmically-bounded length.

Using graph powers

Let us now present the main tool for our reduction, namely graph powers.

Definition 12. Given a connected graph G = (V, E), let i be a positive integer. The i th -power of G, denoted by G i = (V, E i ), is a graph whose set of vertices is the same as for G; two vertices u, v ∈ V are adjacent in G i if, and only if, there exists a uv-path of length at most i in G. Formally,

E i = {{u, v} : 0 < d G (u, v) ≤ i}.
In particular, the graph power G 1 is G, and the graph power G diam(G) is the complete graph K n , where diam(G) = max u,v∈V d(u, v) is the diameter of G. It is folklore that the graph power G i can be computed in O(n ω(1) log i)-time, using fast square matrix multiplication [START_REF] Seidel | On the all-pairs-shortest-path problem in unweighted undirected graphs[END_REF].

Recall that we said in §2.2 that every 1/2-hyperbolic graph G is C 4 -free. Roughly, most of our reduction will consist in checking whether a polylogarithmic number of graph powers of G are C 4 -free as well. This is a necessary condition so that G is 1/2-hyperbolic, as stated below.

Lemma 13. If G is a 1/2-hyperbolic graph, then for every positive integer i, the graph G i is C 4 -free.

Proof. By contradiction, let u, v, x, y be the vertices of an induced quadrangle in G i , for some positive integer i ≥ 1. Without loss of generality, assume that x, y As a consequence, we have by Definition 1 that:

∈ N G i (u) ∩ N G i (v). It follows by Definition 12 that: max{d G (u, x), d G (u, y), d G (v, x), d G (v, y)} ≤ i; and min{d G (u, v), d G (x, y)} ≥ i + 1.
δ(u, v, x, y) = 1 2 [(d G (u, v) + d G (x, y)) -max{d G (u, x) + d G (v, y), d G (u, y) + d G (v, x)}] ≥ 1 2 [2(i + 1) -2i] ≥ 1 which contradicts the fact that G is 1/2-hyperbolic.
Intuitively, the existence of isometric cycles of length l in G yields the existence of induced quadrangles in some graph power G θ(l) ; this shrinking effect is illustrated with Figure 3. As a result, it may be more efficient to search for induced cycles of length 4 in the graph powers rather than computing the length of a longest isometric cycle of G directly.

We emphasize that the converse does not hold: not all the induced quadrangles in G i yield an isometric cycle in the original graph G. For instance, the square graph H 2 1 of the graph H 1 in Figure 1a contains a quadrangle as an induced subgraph (the vertices of which are u, x, v, y), yet H 1 does not contain an isometric cycle of length more than 3. However, we remind that every graph power has to be C 4 -free by Lemma 13 and so, any induced quadrangle that we detect in some graph power is a certificate to prove that the graph is not 1/2-hyperbolic.

We formalize it as follows.

Lemma 14. Let G = (V, E) be a connected graph, and let C l be an isometric cycle of length l = 4p + ε, p ≥ 1, ε ∈ {0, 1, 2, 3} and l = 5. There is an integer i ∈ [p, 2p] such that the graph power G i contains a C 4 as an induced subgraph.

Proof. Let us fix an arbitrary orientation for C l , and choose a 4-tuple u, x, v, y (in clockwise order) such that:

1. if ε = 0: d G (u, x) = d G (u, y) = d G (v, x) = d G (u, y) = p; 2. if ε = 1: d G (u, x) = d G (u, y) = d G (v, x) = p, and d G (v, y) = p + 1; 3. if ε = 2: d G (u, x) = d G (v, y) = p, and d G (u, y) = d G (v, x) = p + 1; 4. if ε = 3: d G (u, x) = d G (u, y) = d G (v, x) = p + 1, and d G (v, y) = p.
An example of such a choice is given in Figure 3. Note that all the above distances are upper-bounded by p + ⌈ε/4⌉. Furthermore, recall that C l is an isometric cycle by the hypothesis. So, we have:

d G (u, v) = d G (x, y) = 2p when ε ∈ {0, 1} 2p + 1 when ε ∈ {2, 3}
Equivalently, we have d G (u, v) = d G (x, y) = 2p + ⌊ε/2⌋. As a consequence, by Definition 12, we have that G i [{u, x, v, y}] is an induced C 4 , for every p + ⌈ε/4⌉ ≤ i ≤ 2p + ⌊ε/2⌋ -1. To prove that such a value of i always exists, it now remains to prove that:

p + ε 4 ≤ 2p + ε 2 -1, G G 3
Edges of G 2 + pseudoloops {(u, 0), (u, 1)} Figure 4: The construction of the graph G [2] .

that is: 2p + ε 2 -1 -p + ε 4 = p + ε 2 - ε 4 -1 ≥ 0.
A straightforward calculation shows that:

ε 2 - ε 4 = -1 if ε = 1 0 otherwise
As a consequence, if ε = 1 then we are done. Otherwise, since l = 4p + 1 > 5 by the hypothesis, then p ≥ 2 and so:

p + ε 2 - ε 4 -1 ≥ 2 -1 -1 ≥ 0.
Note that the only two possible lengths for an isometric cycle of the graph that Lemma 14 does not take into account are 3 and 5. This is not a coincidence, as C 3 and C 5 are the only cycles that are 1/2-hyperbolic by Lemma 10.

Transforming some obstructions into quadrangles

One of the most fundamental step for our reduction was to prove with Lemma 13 that every graph power G i , i ≥ 1, has to be C 4 -free so that a connected graph G is 1/2-hyperbolic. An interesting question on its own is whether it is also a sufficient condition.

We give a negative answer to this conjecture, using the graph H in Figure 5. The graph H is the union of a C 5 and a C 3 that both share a single edge; using the 4-tuple in bold in Figure 5, one can verify that δ(H) ≥ 1. Clearly, H does not contain a quadrangle as an induced subgraph. Moreover, diam(H) = 3 and so, for every i ≥ 3, the graph power H i is a complete graph. Finally, as there is only one couple x, y of H such that d H (x, y) = 3, it follows that the square graph H 2 of H only lacks a single edge to be complete; as a result, H 2 is C 4 -free as well.

The primary aim of this section is now to show that in order to complete our reduction, we solely need to decide whether only one additional graph is C 4 -free: Definition 15. Let G = (V, E) be a connected graph. The graph G [2] = (V [2] , E [2] ) is defined as follows:

1. V [2] ≃ V × {0, 1}; 2. G [2] [V × {0}] ≃ G; 3. G [2] [V × {1}] ≃ G 3 ;
4. ∀u, v ∈ V , the vertices (u, 0) and (v, 1) are adjacent in G [2] if, and only if, d G (u, v) ≤ 2.

In particular, ∀u ∈ V , there is an edge {(u, 0), (u, 1)} ∈ E [2] .

H H 2 H 3 H [2]
Figure 5: A 1-hyperbolic graph whose powers are C 4 -free. A quadrangle in H [2] is drawn in bold.

An illustration of the construction of G [2] is presented in Figure 4. It might help to observe that for every edge of G 2 i.e., for every two distinct vertices u, v such that d G (u, v) ≤ 2, there are exactly two corresponding edges in G [2] , denoted by {(u, 0), (v, 1)} and {(u, 1), (v, 0)}, that connect the sets V × {0} and V × {1}. Every other connecting edge of G [2] is a pseudo-loop {(u, 0), (u, 1)}, for some vertex u ∈ V .

We interpret the role of G [2] as the role of an "intermediate power" between the square graph G 2 and the cube graph G 3 . First, let us prove that it is necessary for G [2] to be C 4 -free so that G is 1/2-hyperbolic.

Lemma 16. If G is a 1/2-hyperbolic graph, then the graph G [2] is C 4 -free.

Proof. By contradiction, let a, b, c, d be the vertices of an induced quadrangle in G [2] . Without loss of generality, we assume that d

G [2] (a, b) = d G [2] (c, d) = 2.
Several cases have to be considered, that we illustrate with Figure 6.

If a, b, c, d ∈ V ×{0}, then there is an induced C 4 in G by Definition 15. Similarly, if a, b, c, d ∈ V ×{1}, then there is an induced C 4 in G 3 by Definition 15. In both cases, this implies that G is not 1/2hyperbolic, by Lemma 13. For all the remaining cases, we claim that there is no vertex u ∈ V such that {(u, 0), (u, 1)} ⊆ {a, b, c, d}.

It easily follows from the fact that N G [2] ((u, 0)) ∪ {(u, 0)} ⊆ N G [2]
((u, 1)) ∪ {(u, 1)}. Thus we can write (a, b, c, d) = ((u, k), (v, k ′ ), (x, j), (y, j ′ )), with {k, k ′ , j, j ′ } = {0, 1} and vertices u, v, x, y are pairwise distinct.

Case 1: k = 0, k ′ = j = j ′ = 1. Here it comes that:

max{d G (u, x) + d G (v, y), d G (u, y) + d G (v, x)} ≤ 2 + 3 = 5, whereas d G (u, v) + d G (x, y) ≥ 3 + 4 = 7.
In other words, δ(G) ≥ δ(u, v, x, y) ≥ 1.

Case 2: k = 1, k ′ = j = j ′ = 0. In such a case: max{d G (u, x) + d G (v, y), d G (u, y) + d G (v, x)} ≤ 2 + 1 = 3, whereas d G (u, v) + d G (x, y) ≥ 3 + 2 = 5. So, δ(G) ≥ δ(u, v, x, y) ≥ 1. Case 3: k = k ′ = 0, j = j ′ = 1. It follows that: max{d G (u, x) + d G (v, y), d G (u, y) + d G (v, x)} ≤ 2 + 2 = 4, whereas d G (u, v) + d G (x, y) ≥ 2 + 4 = 6.
In other words, δ(G) ≥ δ(u, v, x, y) ≥ 1.

Case 4: k = j = 0, k ′ = j ′ = 1. Then we have:

max{d G (u, x) + d G (v, y), d G (u, y) + d G (v, x)} ≤ max{1 + 3, 2 + 2} = 4, whereas d G (u, v) + d G (x, y) ≥ 3 + 3 = 6.
So, we again conclude that δ(G) ≥ δ(u, v, x, y) ≥ 1. (c)

3 3 3 3 (d) 2 1 1 2 (e) 2 3 2 1 (f)
Figure 6: Possible quadrangles in G [2] . Edge weights represent distances in G.

Recall that in order to decide whether a graph is 1/2-hyperbolic, our aim is to check whether all of the three Conditions 3, 4 and 5 of [START_REF] Bandelt | 1-hyperbolic graphs[END_REF] are satisfied, using stronger necessary conditions. So far, we only dealt with Condition 3, developing tools in §3.2.1 and 3.2.2 in order to determine if every cycle of length at least 6 in the graph is bridged. The following two lemmas will show a way to combine the graph G [2] of Definition 15 with the graph powers of Definition 12, in order to ensure that both Conditions 4 and 5 are satisfied as well.

Let us start with Condition 4:

Lemma 17. Let G = (V, E) be a δ-hyperbolic graph, for some δ ≥ 1/2. Suppose G does not satisfy Condition 4. Then G [2] is not C 4 -free, or there exists some positive integer i ≤ 2δ such that G i is not C 4 -free.

Proof. Let u, v ∈ V be such that N (u) ∩ [u, v] is not a clique, and d(u, v) is minimum w.r.t. this property. Let x 1 , y 1 ∈ N (u) ∩ [u, v] such that x 1 and y 1 are not adjacent in G.

• Note that if d(u, v) = 2, then we are done as u, v, x 1 , y 1 are the vertices of an induced C 4 in G.

• Similarly, if d(u, v) = 3, then we have:

1. d(u, x 1 ) = d(u, y 1 ) = 1; 2. d(x 1 , y 1 ) = d(v, x 1 ) = d(v, y 1 ) = 2;
as a consequence, (u, 0), (x 1 , 0), (y 1 , 0), (v, 1) are the vertices of an induced quadrangle in the graph G [2] .

In the sequel, we will assume d(u, v) ≥ 4. Let us define the two uv-shortest paths:

P 1 = u, x 1 , x 2 , x 3 , . . . , x d(u,v)-1 , v and P 2 = u, y 1 , y 2 , y 3 , . . . , y d(u,v)-1 , v
Note that for every i ≤ j we have d(x i , y j ) ≥ d(y i , y j ) = j -i, and in the same way d(x j , y i ) ≥ d(x j , x i ) = ji. We now claim that for every i ≤ j, the inequalities above are strict, or equivalently d(x i , y j ) > ji and d(x j , y i ) > ji. By contradiction, suppose that there is some i ≤ j satisfying d(x i , y j ) = ji. Then in such a case we have x 1 , y 1 ∈ N (u) ∩ [u, y j ], contradicting the minimality of d(u, v). The case when d(x j , y i ) = ji is dealt with similarly. To sum up, by the minimality of d(u, v) we have that for any i ≤ j: d(x i , y j ) > d(y i , y j ) = ji and d(x j , y i ) > d(x j , x i ) = ji.

In particular, for all i, j this yields that x i and y j are pairwise distinct. §3.2.1. 6 . In the sequel, let δ c (G) be a c-factor approximation of the hyperbolicity. Recall that we have δ(G) ≤ δ c (G) ≤ c.δ(G) by the hypothesis. So, if δ c (G) > c/2, then we are done as the graph G is not 1/2-hyperbolic. Let us now assume that δ(G) ≤ δ c (G) ≤ c/2. By Corollary 11, every isometric cycle of G has length upper-bounded by 4δ c (G) + 3 ≤ 2c + 3, which is polylogarithmically upper-bounded.

We then compute all the graph powers G i , for 1 ≤ i ≤ 2δ c (G) + 1. This can be done in subcubictime, by first computing the distance-matrix of G in O(n ω (1) log n)-time (see [START_REF] Seidel | On the all-pairs-shortest-path problem in unweighted undirected graphs[END_REF]). Moreover every G i has to be C 4 -free by Lemma 13. If so, then by Lemma 14, there is no isometric cycle C l of length 6 ≤ l ≤ 4δ c (G) + 3. Consequently, the graph G satisfies Condition 3. Finally, let us build G [2] , which can also be done in subcubic-time using the distance-matrix of G. By Lemma 16, the graph G [2] has to be C 4 -free so that G is 1/2-hyperbolic. If it is indeed the case, then we have:

1. G [2] and all of G i , 1 ≤ i ≤ 2δ c (G) are C 4 -free, hence G satisfies Condition 4 by Lemma 17; 2. G [2] and the square graph G 2 are both C 4 -free and so, G satisfies Condition 5 by Lemma 18.

Thus we can conclude by [START_REF] Bandelt | 1-hyperbolic graphs[END_REF] that G is a 1/2-hyperbolic graph.

Corollary 21. There is a subcubic equivalence between the 1/2-hyperbolic graph recognition problem and the C 4 -free graph recognition problem.

Finding a quadrangle

We will conclude this paper with an improved algorithm for the C 4 -free graph recognition problem, that hence improves the best-known upper-bound on the time complexity of both Problem 2 and Problem 6 by the subcubic equivalence of Corollary 21. While the algorithm proposed in [START_REF] Spinrad | Finding large holes[END_REF] relies on transitive orientation, our algorithm merely reduces the whole Problem 6 to a fast rectangular matrix multiplication.

A quick reminding of the problem of matrix multiplication is given in §4.1, before we present our algorithm to detect an induced quadrangle in §4.2.

Fast rectangular matrix multiplication

The study of fast matrix multiplication mainly focuses on the O(n ω (1) ) time complexity of multiplying two n × n matrices, also known as the square matrix product. Currently, ω(1) is known to be less than 2.3727 [START_REF] Williams | Multiplying matrices faster than coppersmith-Winograd[END_REF]. The rectangular matrix multiplication problem has received less attention, maybe because the product of an n × m matrix with an m × p matrix is known to be reducible to square matrix multiplications, yielding an O(q ω(1)-2 . max{mn, mp, np})-time complexity, for q = min{m, n, p} [START_REF] Huang | Fast rectangular matrix multiplication and applications[END_REF].

On the other hand, there is evidence that faster methods for the rectangular matrix multiplication which do not rely on the square matrix product may exist. This is known to be the case even for truly practical improvements of the matrix multiplication such as the Strassen algorithm and its variations [START_REF] Huss-Lederman | Implementation of strassen's algorithm for matrix multiplication[END_REF][START_REF] Knight | Fast rectangular matrix multiplication and QR decomposition[END_REF]. As stated below, the conjecture is (numerically) true w.r.t. the best known algorithms for square and rectangular matrix multiplications. Lemma 22 ([12,[START_REF] Huang | Fast rectangular matrix multiplication and applications[END_REF][START_REF] Franc | Faster algorithms for rectangular matrix multiplication[END_REF][START_REF] Williams | Multiplying matrices faster than coppersmith-Winograd[END_REF]). Let r ≥ 1 be a rational number. There exists a non-decreasing function ω : [1; +∞[→ [2.3727; +∞[ such that multiplying an n × n r matrix with an n r × n matrix can be done in O(n ω(r) )-time.

Furthermore, ω(2) ≤ 3.26, and for every r ≥ 1 we have ω(r) ≤ r + ω(1) -1.

Note that reducing the rectangular matrix product to square matrix multiplications would have only yielded ω(2) ≤ 3.3727.

A more efficient method is known for sparse matrices (e.g. see [START_REF] Yuster | Fast sparse matrix multiplication[END_REF]).

An algorithm to count quadrangles in a graph

In this section, we essentially apply the local characterization of Fact 7. There are two main steps of computation in our algorithm, that are described below.

Fact 23 ([36]). Given a graph G = (V, E), let A = (A u,v ) u,v∈V be the adjacency matrix of G.

For every pair u, v ∈ V , we have

A 2 u,v = |N (u) ∩ N (v)|. Hence, d(u, v) = 2 if, and only if, u = v, A u,v = 0 and A 2 u,v = 0. Proof.
By the definition of matrix multiplication, we have for every pair u, v ∈ V that:

A 2 u,v = x∈V A u,x A x,v = x∈V I {{x,u}∈E} I {{x,v}∈E} = x∈V I {x∈N (u)} I {x∈N (v)} = x∈V I {x∈N (u)∩N (v)} = |N (u) ∩ N (v)|.
Moreover, d(u, v) = 2 if, and only if, u = v, u and v are not adjacent in G (e.g. A u,v = 0), and

N (u) ∩ N (v) = ∅. Clearly, we have that N (u) ∩ N (v) = ∅ if, and only if, A 2 u,v = 0.
Lemma 24. Given a graph G = (V, E), let T = (T u,e ) u∈V,e∈E be such that T u,e = I {e⊆N (u)} for every u ∈ V, e ∈ E.

For every pair u, v ∈ V , we have

T T ⊤ u,v = |{e ∈ E : e ⊆ N (u) ∩ N (v)}|. Proof.
Similarly to the proof of Fact 23, we have by the definition of matrix multiplication that for every pair u, v ∈ V :

T T ⊤ u,v = e∈E T u,e T ⊤ e,v = e∈E T u,e T v,e = e∈E I {e⊆N (u)} I {e⊆N (v)} = e∈E I {e⊆N (u)∩N (v)} = |{e ∈ E : e ⊆ N (u) ∩ N (v)}|.
Combining Fact 23 and Lemma 24, we can now rely on Fact 7 in order to detect, to count and to output induced quadrangles in the graph as follows.

Proposition 25. Counting the number of induced quadrangles in a a graph G, and returning an induced C 4 of G if any, can be done in O(n ω(log n m) ) = O(n 3.26 )-time.

Proof. First, it is straightforward that we can compute the adjacency matrix A of G in quadratic-time. Using A, we can compute the matrix T = (I {e⊆N (u)} ) u∈V,e∈E , hence the transpose matrix T ⊤ as well, as they are defined in Lemma 24, in O(nm)-time.

Let us now compute A 2 and T T ⊤ . This can be done, respectively, in O(n ω(1) ) = O(n 2.3727 )-time and in O(n ω(log n m) ) = O(n ω(2) ) = O(n 3.26 )-time by Lemma 22. By Fact 7, G is C 4 -free if, and only if, for every pair u, v ∈ V of non-adjacent vertices, we have that N (u) ∩ N (v) is a clique, e.g. that:

|{e ∈ E : e ⊆ N (u) ∩ N (v)}| = |N (u) ∩ N (v)|(|N (u) ∩ N (v)| -1) 2 .
This is equivalent to have that T T ⊤ u,v = A 2 u,v (A 2 u,v -1)/2 by Fact 23 and Lemma 24. Hence, it can be checked with an enumeration of all the possible pairs u, v ∈ V , in quadratic-time.

We actually note that if there is some pair u, v ∈ V of non-adjacent vertices such that T T ⊤ u,v < A 2 u,v (A 2 u,v -1)/2, then there are exactly A 2 u,v (A 2 u,v -1)/2 -T T ⊤ u,v induced quadrangles of G which contain this pair of vertices (that is one quadrangle for each of the missing edges in G[N (u) ∩ N (v)]). Consequently, there are exactly 1/4 u,v∈V (1 -A u,v )(A 2 u,v (A 2 u,v -1)/2 -T T ⊤ u,v ) induced quadrangles in the graph, which can also be computed in quadratic-time, by an enumeration of all the possible pairs u, v ∈ V .

To conclude, observe that if T T ⊤ u,v = A 2 u,v (A 2 u,v -1)/2 for some pair u, v ∈ V of non-adjacent vertices, then it is straightforward to compute an induced quadrangle of G containing u, v in quadratic-time.

We remind the reader that there is only evidence that a fast rectangular matrix product can be computed faster than up to the reduction to fast square matrix multiplications. However, we want to highlight that, from a theoretical point of view, our algorithm for detecting an induced quadrangle is never slower than the algorithm of [START_REF] Spinrad | Finding large holes[END_REF]. The dominant term for the complexity of our algorithm is indeed the fast rectangular matrix multiplication T T ⊤ (e.g. Lemma 24), which can be computed in O(mn ω(1)-1 )time in the worst-case, using the reduction to fast square matrix products that we described earlier in §4.1. In comparison, the time complexity of the algorithm of [START_REF] Spinrad | Finding large holes[END_REF] is O(n ω(1)+1 ).

Also, we emphasize that for graphs with few C 3 's, a speed-up for the computation of T T ⊤ can be achieved using the results from [START_REF] Yuster | Fast sparse matrix multiplication[END_REF] for sparse matrix multiplication. Indeed, the number of non-zero elements in the matrix T is exactly 3.t(G), where t(G) denotes the number of C 3 in the graph.

Conclusion

In this work, we proved an interesting equivalence between the complexity of the purely metric problem of recognizing 1/2-hyperbolic graphs, and the purely structural problem of detecting an induced quadrangle in a graph. This shows a surprising gap in the complexity for recognizing graphs with small hyperbolicity, as in comparison there is a linear-time algorithm to decide whether a graph is 0-hyperbolic.

Our reduction being subcubic, it remains open whether 1/2-hyperbolic graphs can be recognized in linear-time, for some classes of graphs for which detecting an induced quadrangle is easy, like for instance planar graphs [START_REF] Eppstein | Subgraph isomorphism in planar graphs and related problems[END_REF]. Also, it would be nice to extend our results to find a better upper-bound on the complexity of the problem of deciding if a graph is 1-hyperbolic. Note that this latter problem might be easier than the recognition of 1/2-hyperbolic graphs, as the true difficulty may only lie in the distinction between graphs with hyperbolicity exactly 1 and exactly 1/2. Any recognition algorithm in O(f (n))-time for 1-hyperbolic graphs would furthermore yield a 4-factor approximation algorithm for the hyperbolicity that runs in Õ(f (n) + n ω(1) )-time.

Figure 1 :

 1 Figure 1: The six forbidden isometric subgraphs.

  u

Figure 2 :

 2 Figure 2: An illustration of the linear-time reduction of Proposition 8.

3. 1 Proposition 8 .

 18 Reducing the detection of a C 4 to the recognition of a 1/2-hyperbolic graph There is a linear-time reduction from the C 4 -free graph recognition problem to the problem of deciding whether a graph is 1/2-hyperbolic.

Figure 3 :

 3 Figure 3: Shrinking long isometric cycles into quadrangles.

We use the symbol I instead of the classical symbol δ for the Kronecker delta in order to prevent confusion with hyperbolicity.

The notation Õ(f (n)) is for a complexity f (n) • log O(1) n.

The term min{nm, n ω[START_REF] Bandelt | 1-hyperbolic graphs[END_REF] log n} in the complexity comes from the computation of the all-pairs shortest-paths in the graph (see[START_REF] Seidel | On the all-pairs-shortest-path problem in unweighted undirected graphs[END_REF] for an algorithm in Õ(n ω(1) )-time for the problem).

The authors in[START_REF] Fournier | Computing the gromov hyperbolicity of a discrete metric space[END_REF] actually claim a O(n 2 )-time complexity for their algorithm, but it takes as inputs discrete metric spaces and so, it does not apply to graphs directly. To apply their results on graphs, we can use a θ(log n)-additive approximation of the all-pairs shortest-paths, which can be computed in Õ(n 2 )-time (see[START_REF] Dor | All-pairs almost shortest paths[END_REF]).

Recall that a graph is 0-hyperbolic if, and only if, it is a block-graph i.e., a graph whose biconnected components are complete subgraphs[START_REF] Bandelt | Distance-hereditary graphs[END_REF][START_REF] Howorka | On metric properties of certain clique graphs[END_REF].

A careful reader will remark that the choice of c determines the maximum number of calls in the reduction to the algorithm for detecting an induced quadrangle. There is a trade-off between this number and the running-time of the c-factor approximation algorithm.

Acknowledgments

We wish to thank the referees for their reading of the first version of this manuscript, and their useful comments. We would also like to thank Frédéric Havet and Fatima Zahra Moataz for helpful comments on this work.

This work has been partially supported by ANR project Stint under reference ANR-13-BS02-0007, ANR program "Investments for the Future" under reference ANR-11-LABX-0031-01, and by European project FP7 EULER (Grant No.258307).

Also, note that for all i, δ(u, v, x i , y i ) = d(x i , y i )/2 and so, we have that for every i:

Let l ≥ 3 be the least index greater than 2 such that d(x l , y l ) ≤ l -1. One has to observe that since for all i, d(x i , y i ) ≤ 2δ, it holds that l ≤ min{2δ + 1, d(u, v) -1}. In such a case:

Consequently, x 1 , y 1 , x l , y l are the vertices of an induced quadrangle in G l-1 .

Let us finally prove with Lemma 18 that we can verify whether Condition 5 is satisfied in the same way as we verified Condition 4 in Lemma 17.

Lemma 18. Let G = (V, E) be a connected graph that does not satisfy Condition 5. Then there is an induced C 4 in the graph G [2] , or there is an induced C 4 in the square graph G 2 .

Proof. We proceed by contradiction. Let us assume that one of the graphs of Figure 1 is an isometric subgraph of G. For each of the forbidden graphs of Condition 5, we will only consider the 4-tuple of vertices that are drawn in bold in Figure 1, denoted by u, y, v, x.

Cases 1a and 1b

One can easily check that in both cases, the four vertices in bold are the vertices of an induced quadrangle in the square graph G 2 .

Case 1c

Observe that d(u,

, 0) are the vertices of an induced quadrangle in G [2] . A contradiction.

Case 1d

We have that all distances but d(u, v) equal 2, and that d(u, v) = 4. Therefore, (u, 1), (y, 0), (v, 1), (x, 0) are the vertices of an induced C 4 in G [2] . Again, this is not possible.

Case 1e

Observe that d(u, x) = d(u, y) = 2, d(x, y) = 4, and all the remaining distances are equal to 3. As a consequence, (u, 0), (y, 1), (v, 1), (x, 1) are the vertices of an induced quadrangle in G [2] , which contradicts the fact that G [2] is C 4 -free.

Case 1f

The vertices (u, 1), (y, 1), (v, 1), (x, 1) induce a C 4 in G 3 , hence in G [2] , that is once more a contradiction.

To sum up, we obtain as a byproduct of our reduction, and especially of Lemmas 13, 14, 16, 17 and 18, the following new characterization of 1/2-hyperbolic graphs:

and only if, every graph power G i , i ≥ 1, is C 4 -free, and the graph G [2] is C 4 -free.

The condition is necessary by Lemmas 13 and 16, and it is sufficient by Lemmas 14, 17 and 18.

The reduction

Theorem 20. There is a subcubic reduction from the 1/2-hyperbolic graph recognition problem to the problem of detecting an induced quadrangle in a graph.

Proof. Let G = (V, E) be a connected graph. Since there exists a linear-time algorithm to recognize 0-hyperbolic graphs 5 , we will assume for the proof δ(G) > 0, or equivalently δ(G) ≥ 1/2. Let us fix any c = log O(1) n, c ≥ 1, such that we can compute a c-factor approximation of the hyperbolicity in subcubic-time. Three possible choices for c are given in Lemma 9, and two others ones are discussed in


Methodological Proposals for Designing Federative Platforms in Cultural Linked Open Data: the example of MoDRef Antoine Courtin (University Paris Ouest Nanterre La Défense) Jean-Luc Minel (MoDyCo, University Paris Ouest Nanterre La Défense, CNRS)

As part of the on-going Labex project Past in the present , our proposal aims at highlighting the organizational issues of linked data projects that have to deal with pluri-institutional contexts, among which libraries. First, we will discuss what is at stake. Second, we will present a methodology based on the building of several diagrams which highlight technical, conceptual, and organizational obstacles. We will also address the issues of designing and producing an information system intended to ensure the transmission of scientific skills, the exploitation of major vocabularies, associated to specific vocabularies, by foreign institutions and the harmonizing or building of bridges between heterogeneous descriptions.

The opportunities afforded by digital technologies for digitizing objects, processing digital data and displaying these data and metadata have led patrimonial institutions (libraries, museums, archives) and research units to build production lines and then data repositories. In addition to questions of professional standards, the visibility of these data repositories is an urgent concern within patrimonial institutions at the present time: 2013 was remarkable for the number of initiatives, notably supported by the Ministère de la Culture et de la Communication. In France as in other countries, this mass of projects had led to various proposals being put forward. Some of them focus on building conceptual models, sometimes called ontologies, and can be sharply distinguished from one another by their disciplinary origins.

Our starting assumption is based on the use of languages from the semantic Web, and especially formal languages such as RDF, RDFS and OWL (Berners-Lee et al. 2005), to produce digital tools for data processing, to allow real interoperability between the various repositories created (Hyvönen 2012) and then to form linked data. These tools have not only a documentary ambition but should also give rise to new research perspectives by increasing the sources of information.

At first sight, the crucial concern of patrimonial institutions is the insertion of the data produced by an institution within an ecosystem, beyond disciplinary borders. From an operational point of view, the concept of interoperability is the most widely used (Hyvönen 2012), with a distinction between syntactic interoperability, which deals with data exchange standards and digitized annotations, and semantic interoperability, which concerns the semantics of annotations. We consider, however, that designing a platform should be envisaged through every dimensions of the ecosystem and not only through interoperability. More specifically, specialized descriptive vocabularies and authority lists are the cornerstone of developments in the patrimonial field. However, these resources depend mainly on the SKOS language, which is in fact used as a standard and has become one of the main languages of the semantic web (Gandon et al. 2012). In January 2014, around 400 specialized vocabularies had been recorded (Vatant et al. 2013). Moreover, the boundaries between conceptual models and vocabularies are not clearly defined: FRBR is designed as a vocabulary (Vatant et al. 2013) although we would argue that it is more a conceptual model. Some ontologies such as the CIDOC-CRM or HADOC (Harmonisation de la production des données culturelles) claim to embrace Cultural Heritage as a whole and to transcend institutional borders (museums, libraries, archives).

In order to tackle this multidimensional complexity, i.e. conceptual, technical and organizational features, we have designed a methodology that is able to both identify obstacles and provide some solutions.

Our presentation will be based on the work conducted since 2012 as part of the project group Modèles, Référentiels et Culture Numérique (ModRef) in the labex Past in the present (http://www.passespresent.eu/). This labex associates 7 research units and 4 patrimonial institutions, including 3 libraries (Bibliothèque nationale de France, Bibliothèque de documentation internationale contemporaine, Bibliothèque Éric-Dampière). The advantage of these libraries for the ModRef project is that they represent various environments, scales, data models and usages and therefore give us a broad vision of the issues involved. Moreover, these issues, which are specific to libraries engaged in linked open data, have to be, in our case, recontextualized with other patrimonial institutions in order to identify the possible conceptual, organizational and technical divergences and convergences. The question is no longer one of considering linked data inside a single institution the library , but of considering it as an exchange institution from the very beginning. By taking this global approach to digital humanities, the ModRef group aims to work on the interoperability of multimodal corpora (sounds, texts, images, videos), which are produced by the partners, and with other data repositories and then to better insert them in the linked data ecosystem. Through it, we wish to show partner institutions the interest of using LOD by highlighting the gains within the labex and inserting them in a long term perspective.

Five descriptive dimensions have to be considered: concept, technologies, organization, licence issues and user experience. Three of them will be developed as examples. These dimensions have nevertheless to be recontextualized with respect to the intended aims of data reuse and enrichment by placing usages at the heart of the thinking. We will focus on the challenges created by the multidimensionality of information within the patrimonial field and by the variety of institutions involved and anticipated enduses. To handle this multidimensionality, an approach based on the parsing of complex systems appears appropriate (Mitchell 2009).

Concerning the conceptual dimension, we have already mentioned the variety of models resulting from different disciplinary traditions. Those ones concern on the same time the conceptual (or structural) model and the XML syntax. We contend that it would be more advisable to separate the two notions: on the one hand the conceptual model, and on the other the syntactic format with the language used to write the grammar of the model. We have to point out that it is difficult to forecast what the main standard (either normalized or actually used) will be in the five next years. In France, the Bibliothèque nationale de France seems to be tempted by the FRBR, while the Ministère de la Culture promotes the use of the harmonized model created through the HADOC program for producing cultural data, and the Archives Nationales, part of the ICA/EGAD working group, has chosen to create an OWL-ontology. At the European level, Europeana promotes its own EDM model. These are just a few examples among many.

As this instability has to be taken into consideration, the aim of our methodological proposals is to ensure the adaptability of the target system. This multiplicity of initiatives, in addition to the question of choice, makes it extremely complex to address the conceptualization of patrimonial information. The pedagogical aspect is also an important element in the organizational dimension and has to be considered in such a project.

The technological dimension is more or less structured, as plenty of digital tools are dedicated to the management and exploitation of digitized data. The functionalities of these tools are broad, ranging from cataloguing to the management of enquiries, the integration of data curation and the maintenance of thesauri or authority lists. By considering only the technical part, these tools can be fully proprietary.

This implies in general a dependence on ad hoc or totally open formats and on database management systems with a more or less common format. Often, these two possibilities coexist side by side within the same institution. We argue that the main criterion has to be the exchange model or rather, the possibilities of displaying and then reusing the data, that are offered by existing systems. This exchange model includes four levels. The first level concerns simply the possibility of exporting or dumping data to a more or less common format, generally XML. The second one deals with the exposition of data through a protocol such as OAI-PMH. The third level offers a single public and documented API (application programming interface), while the last one gives access to a SPARQL-endpoint according to W3C recommendations and guarantees insertion within the LOD system.

Our work at ModRef is a good illustration of these various degrees of involvement for data exposition.

This technological choice arises not from a technical challenge but from the conjunction of multiple organizational and features which join altogether, as it seems, in order to overstep the data appropriation and also to expose them.

The organizational dimension concerns both the description of the power of each organization (patrimonial institutions, research units and supervisory authorities) and the description of the participants (curators, researchers, users). This dimension is the hardest one to perceive since many factors that are difficult to categorize come into play, as they are part of a dynamic process (Reix et al.

2011).

In order to find a solution which could be adapted to the needs and constraints of the partner institutions, we will produce several diagrams. Each of them will represent the different dimensions mentioned, to make the conjunction or the dispersion of the projects easy to visualize.

In order to build these diagrams, we have designed a workflow. In the first step, information was collected in the usual way by asking the members involved to fill in analytical grids during interviews.

In the second step, the grids as a whole were submitted to all the partners for validation, thus enabling them to correct or complete some features of their own project thanks this comprehensive overview of all the projects. While this two-step approach reduces the process of collecting and consolidating information but it takes part of the organizational learning. The diagrams are created semiautomatically. For obvious reasons of flexibility and reuse, a processing line has been implemented, so that some actions can be automatized. All the data are entered in a spreadsheet and then classified and quantified. A JSON file is then generated to make data manipulation easier thanks to the D4.js javascript library which also makes it possible to create SVG exports that are easily handleable with Inkscape.

Figures 1 and2 show two examples of the diagrams produced. This methodology makes it possible to identify the possible obstacles and to integrate the different participants thanks to a pedagogical approach (training sessions, frequent workshops, heuristic diagrams), but above all to make recommendations to each of our partners. This is the basis of the production of a proof of concept which will start in early April.

Bibliography: [ GANDON et al., 2012]

Figure

  Figure 1: Labex ecosystem

[

  BERNERS-LEE et al., 2005] BERNERS-LEE, Tim, DIETER, Fensel, HENDLR, James, & LIEBERMAN, Henry, Spinning the Semantic Web: Bringing the World Wide Web to Its Full Potential , Édition, Wolfgang Wahlster The MIT Press, 2005. [HYVÖNEN 2012] HYVÖNEN, Eero, Publishing and Using Cultural Heritage Linked Data on the Semantic Web , Morgan & Claypool Publishers, 2012.

  GANDON, Fabien, FARON-ZUCKETR, Catherine & CORBY, Olivier, O. Le Web sémantique : comment lier les données et les schémas sur le web ?, Dunod, 2012. [MITCHELL 2009] MITCHELL, Melanie, Complexity: A Guided Tour, Oxford: Oxford University, 2009. [REIX 2011] REIX, Robert, FALLERY, Bernard, KALIKA Michael, & ROWE Frantz, Systèmes d'information et management des organisations, Paris, Vuibert, 2011 [VATANT et al.,] VATANT Bernard, VANDEBBUSSCHE, Pierre-Yves (2013), Linked Open Vocabularies , http://lov.okfn.org/data (consulted on 4th March 2014)


Denys Dutykh
email: denys.dutykh@univ-savoie.fr

Elena Tobisch
email: elena.tobisch@jku.aturl

FORMATION OF THE DYNAMIC ENERGY CASCADES IN QUARTIC AND QUINTIC GENERALIZED KDV EQUATIONS

Keywords: energy cascade, modulational instability, Fourier power spectrum, Korteweg-de Vries equations MSC: [2010]76B15 (primary), 76B55, 76E20 (secondary) PACS: 47.35.-i, 47.20.Cq, 47.11.Kb

In this study we investigate the formation of dynamical energy cascades in higher order KdV-type equations. In the beginning we recall what is known about the dynamic cascades for the classical KdV (quadratic) and mKdV (cubic) equations. Then, we investigate further the mKdV case by considering a richer set of initial perturbations in order to check the validity and persistence of various facts previously established for the narrow-banded perturbations. Afterwards we focus on higher order nonlinearities (quartic and quintic) which are found to be quite different in many respects from the mKdV equation. Throughout this study we consider both the direct and double energy cascades. It was found that the dynamic cascade is always formed, but its formation is not necessarily accompanied by the nonlinear stage of the modulational instability. Direct cascade structure remains invariant regardless the size of the spectral domain. In contrast, the double cascade shape can depend on the size of the spectral domain, even if the total number of cascading modes remains invariant. Results obtained in this study can be potentially applied to plasmas, free surface and internal wave hydrodynamics.

Introduction

When we want to describe an open or a closed physical system, the main question is to describe the energy flux inside this system and with surrounding environment. The energy transport along the wavenumbers in Fourier space is generally called the energy cascade. An elegant idea to describe this cascade in turbulent flows was first proposed by Richardson in 1922 [START_REF] Richardson | Weather prediction by numerical process[END_REF]. His empirical description was put by the author in the form of a verse:

Big whirls have little whirls, Which feed on their velocity, And little whirls have lesser whirls, And so on to viscosity.

In this poetic way Richardson described the energy transport among turbulent vortexes over the scales which ends by the dissipative region. This semi-empirical argument was made more accurate by Kolmogorov in his famous 1941 paper (whose English translation can be found in [START_REF] Kolmogorov | The Local Structure of Turbulence in Incompressible Viscous Fluid for Very Large Reynolds Numbers[END_REF]) where he proposed the universal energy spectrum ∼ ℓ 5 3 for the strong homogeneous isotropic turbulence (here ℓ is characteristic size of a vortex). A similar approach applied to weakly nonlinear wave systems resulted in the development of the socalled Weak (or wave) Turbulence Theory (WTT) [START_REF] Zakharov | Kolmogorov Spectra of Turbulence I. Wave Turbulence. Series in Nonlinear Dynamics[END_REF] where the spectrum is not universal anymore and it depends on the dispersion function. However, the spectrum shape still remains a powel law as in the strong turbulence theory. In terms of the nonlinearity parameter ε the strong turbulence theory corresponds to ε ST ∼ O(1) while the WTT is situated in the range ε W ∼ O (10 -2 ).

The model of the dynamic energy cascade for the case of intermediate (moderate) nonlinearities ε M ∼ O(10 -1 ) was proposed quite recently in 2012 [START_REF] Kartashova | Energy spectra of 2D gravity and capillary waves with narrow frequency band excitation[END_REF] and studied analytically in [START_REF] Kartashova | Energy transport in weakly nonlinear wave systems with narrow frequency band excitation[END_REF][START_REF] Kartashova | Time scales and structures of wave interaction exemplified with water waves[END_REF]. Since the dynamic energy cascade model is based on the Modulational Instability (MI) mechanism, the first developments were made the the case of the Nonlinear Schrödinger (NLS) equation and its modifications. The spectrum shape is deduced from the Incremental Chain Equations (ICE) which strongly relies on the knowledge of the instability interval. Fortunately this information is readily available for NLS-type equations in the literature.

On the other hand, the MI can be encountered in other types of model equations. It is important to study the dynamic energy cascade formation in these models as well. The present article is entirely devoted to some generalized Korteweg-de Vries (KdV)-type equations. The celebrated original KdV equation was derived for the first time for surface waves in shallow waters [START_REF] Boussinesq | Essai sur la theorie des eaux courantes[END_REF][START_REF] Korteweg | On the change of form of long waves advancing in a rectangular canal, and on a new type of long stationary waves[END_REF] in order to explain the phenomenon of solitary waves:

KdV(u) ≐ u t + u xxx + βuu x = 0. (1.1)
However, it is known that the classical KdV equation 1.1 does not possess the MI. Later some extended versions of the KdV equation were derived for both surface [START_REF] Marchant | The extended Korteweg-de Vries equation and the resonant flow of a fluid over topography[END_REF] and internal [START_REF] Grimshaw | Internal Solitary Waves[END_REF] waves. By making appropriate changes of variables, it can be reduced to the following modified (m)KdV equation:

mKdV(u) ≐ u t + u xxx + βu 2 u x = 0. (1.2)
It is known that equation (1.2) is integrable and it possesses the MI for β > 0. For negative values of parameter β < 0 its behaviour is similar to the KdV in the respect of the MI. Formally all these model equations can be encompassed into a single gKdV framework:

gKdV(u) ≐ u t + u xxx + (αu + βu 2 + δu 3 + γu 4 )u x = 0, (1.3)
which generates the KdV, mKdV, quartic and quintic gKdV equations for particular choices of coefficients α, β, δ and γ. Quartic and quintic gKdV equations will be studied extensively numerically below.

In general, there are only few known mathematical facts about higher order KdV-type models. The global well-posedness of the quartic gKdV equation in some critical spaces was shown in [START_REF] Tao | Scattering for the quartic generalised Korteweg-de Vries equation[END_REF], while the stability of periodic travelling waves in the gKdV equation was studied in [START_REF] Bronski | The Modulational Instability for a Generalized Kortewegde Vries Equation[END_REF][START_REF] Bronski | An index theorem for the stability of periodic travelling waves of Korteweg-de Vries type[END_REF].

As we already mentioned above, the shape of the energy spectrum was computed in the NLS-type equations based on the explicit knowledge of the instability interval with finite measure. In the case of the KdV-type equations and nonlinearity of order nonlinearities O(10 -1 ) such finite intervals do not exist, since any mode with the wave vector k 0 > 0 is modulationally unstable (if the equation has the MI, of course). This fact prevents the direct transposition of NLS predictions to the family of KdV-type equations. Nevertheless, we decided to study the dynamic energy cascades in several KdV-type models numerically.

In general, the MI is an effect which describes a special type of the instability of a single spectral component subject to narrow band excitation in an experiment (regardless whether it is numerical or laboratory). In our previous investigations [START_REF] Dutykh | Direct dynamical energy cascade in the modified KdV equation[END_REF][START_REF] Dutykh | Observation of the Inverse Energy Cascade in the modified Korteweg-de Vries Equation[END_REF] we followed this ideology and all the numerical experiments toward the observation of the direct and inverse cascades had only two spectral harmonics in the initial condition (i.e. the base wave k 0 along with its modulation K 0 ≪ k 0 ).

On the other hand, in real-world laboratory experiments it is extremely difficult to excite precisely only two spectral harmonics. It is always a finite range which appears. Consequently, it is interesting to study this situation in numerical experiments as well in order to determine the limits of the survivability of the dynamical energy cascade. Additional motivation comes from the fact that the so-called Benjamin-Feir Index (BFI) [START_REF] Janssen | Nonlinear four-wave interactions and freak waves[END_REF], which characterizes the likelihood of freak wave formation in an open ocean, is also based on the effect of the MI in the presence of a fairly broad spectrum. There is a direct connection between the BFI and the increment chain equations which describe the cascade formation [START_REF] Tobisch | Energy spectrum of ensemble of weakly nonlinear gravity-capillary waves on a fluid surface[END_REF]. It should be noted that the BFI was introduced, strictly speaking, for surface waves in deep water which are described by the NLS-type equations. However, this notion might be transposed to the mKdV case as well, since the analytical bridges between NLS and (m)KdV are well studied [START_REF] Grimshaw | Wave group dynamics in weakly nonlinear long-wave models[END_REF] (and the references therein).

Even if historically the KdV equation (and related models) was proposed first as a model equation for surface waves, later it found applications in many other fields such as plasma physics, acoustic and internal waves in the ocean. That is why the study of this equation along with its various modifications is important. The big advantage of the classical KdV (1.1) and mKdV (1.2) equations consists in their exceptional mathematical propertiesi.e. the integrability, which allows a deep mathematical study. However, even in this case it does not allow to describe exactly the properties of the dynamical energy cascade. If we had a closed form analytical solution u(x, t) than we could develop it in a Fourier series

u(x, t) ∼ +∞ j=-∞ c j (t)e ikx , c k (t) ∶= u(x, t)e -ikx dx.
Then, the Fourier spectrum is given by the graph of the application k ↦ c k (t) 2 . Unfortunately, even for integrable equations we do not always have closed form solutions (with notable excpetion of solitons and cnoidal waves). The modern notion of integrability is related to the construction of the Lax's pair or of conserved quantities (in the number equal to the number of the degrees of freedom, i.e. infinity for PDEs). There is no general method to find a Lax's pair. Thus, the integrability does not always yield the solvability of an equation in practice. Several examples can be found in [START_REF] Shabat | Computable Integrability. Chapter 1: General notions and ideas[END_REF]. Consequently, the priveleged method of studying the non-integrable and even integrable, but not solvable equations is the numerical simulation.

The formation of the dynamical energy cascade in the integrable mKdV equation (1.2) was studied numerically in our previous papers [START_REF] Dutykh | Direct dynamical energy cascade in the modified KdV equation[END_REF][START_REF] Dutykh | Observation of the Inverse Energy Cascade in the modified Korteweg-de Vries Equation[END_REF]. However, it was done for narrow initial perturbations in the Fourier space, since originally it was discovered for the NLS equation which is valid only in this narrow band approximation [START_REF] Kartashova | Energy spectra of 2D gravity and capillary waves with narrow frequency band excitation[END_REF]. On the other hand, the KdV equation does not have limitations on the spectral band, which allows us to study this equation more extensively with broader perturbations.

The present article is organized as follows. In Section 2 the mKdV equation is studied subject to broader initial perturbations. Quintic and quartic higher order modifications of the KdV equation are considered in Section 3. Finally, the main conclusions of the present study are outlined in Section 4.

mKdV equation with broad spectrum initial perturbation

In order to investigate the broader perturbations we considered the following set of numerical experiments which generalize those presented in [START_REF] Dutykh | Direct dynamical energy cascade in the modified KdV equation[END_REF][START_REF] Dutykh | Observation of the Inverse Energy Cascade in the modified Korteweg-de Vries Equation[END_REF]. Here again, in order to solve numerically the mKdV equation on a periodic domain we use the classical Fouriertype pseudo-spectral method [START_REF] Boyd | Chebyshev and Fourier Spectral Methods[END_REF][START_REF] Trefethen | Spectral methods in MatLab[END_REF]. All the derivatives are computed in the Fourier space, while all the nonlinear products are performed in the physical space (with the linear CPUtime, i.e. O(N), where N is the number of collocation points necessarily equal to the number of Fourier modes). Thanks to the FFT algorithm [START_REF] Frigo | FFTW: An adaptive software architecture for the FFT[END_REF][START_REF] Frigo | A fast Fourier transform compiler[END_REF][START_REF] Frigo | The Design and Implementation of FFTW3[END_REF] the passage between these two representations is done in the super-linear time O(N log(N)), which determines the overall algorithm complexity (per time step) O(mN log(N)), m ∼ 1 being the number of FFTs needed to evaluate the right-hand side. For the dealiasing we used the classical 2 3-rule [START_REF] Trefethen | Spectral methods in MatLab[END_REF] which was combined (when necessary) with the Fourier smoothing method proposed in [START_REF] Hou | Computing nearly singular solutions using pseudo-spectral methods[END_REF] for more delicate treatment of higher frequencies. time was done with the embedded adaptive 5 th order Cash-Karp Runge-Kutta scheme [START_REF] Cash | A variable order Runge-Kutta method for initial value problems with rapidly varying right-hand sides[END_REF] with the adaptive PI step size control [START_REF] Hairer | Solving Ordinary Differential Equations II. Stiff and Differential-Algebraic Problems[END_REF]. We note that for the numerical simulation of the gKdV equation one needs to set more stringent tolerances, because of the presence of highly nonlinear products. The accuracy of dynamical computations was checked by following, for example, the L 2 norm of the solution u(x, t) which is one of the invariants of the (g,m)KdV dynamics. In all the experiments this norm was conserved up to the 8 th digit with smaller oscillations around the mean value.

Direct cascade

The numerical set-up used in this study is a direct generalization of the test case used also earlier in [START_REF] Grimshaw | Short-Lived Large-Amplitude Pulses in the Nonlinear Long-Wave Model Described by the Modified Korteweg-De Vries Equation[END_REF]. We consider the following initial condition posed on a periodic domain

[-ℓ, ℓ] = -π k 0 , π k 0 : u(x, 0) ≡ u 0 (x) = a 1 + δ j sin(jK 0 x) sin(k 0 x), (2.1)
where a is the base wave amplitude, δ is the perturbation magnitude and the wavenumbers k 0 , K 0 and j are chosen such that their ratio k 0 (jK 0 ) ∈ Z. The last constraint comes from the periodicity conditions on the initial data. Moreover, the spectral gap between the base wave k 0 and its modulation K 0 contains two orders of magnitude (see Table 1 for the values of parameters). When we perturb the base wave according to (2.1) with a few modes we have to keep in mind that the pertubation has to be different from the base wave at least with one order of magnitude. Taking into account this constraint along with k 0 (jK 0 ) ∈ Z, we obtain that for our numerical set-up j is roughly limited by 10.

The case j ≡ 1 corresponds to the computations already discussed in [START_REF] Grimshaw | Short-Lived Large-Amplitude Pulses in the Nonlinear Long-Wave Model Described by the Modified Korteweg-De Vries Equation[END_REF][START_REF] Dutykh | Direct dynamical energy cascade in the modified KdV equation[END_REF][START_REF] Dutykh | Observation of the Inverse Energy Cascade in the modified Korteweg-de Vries Equation[END_REF]. The values of parameters are given in the Table 1. On Figure 1 we show the corresponding pertubed initial conditions. The case Figure 1(a) corresponds to j = 1. The Fourier spectrum on the bottom panel shows three points which correspond to the base wave k 0 (the most energetic mode) and two side bands k 0 ± K 0 . On Figure 1(b) we depict the perturbation by k 0 ± K 0 , k 0 ± 2K 0 , k 0 ± 3K 0 and k 0 ± 4K 0 modes (in total nine points on the bottom panel). Finally, the last Figure 1(c) corresponds to j = 1, 2, 3, 4, 6, 8 and 10 (counting 15 modes in total).

The evolution of three initial conditions from Figure 1 is simulated using the mKdV equation (1.2). The numerical snapshots taken at the same moment of time t = 160.0 are Numerical solution of the mKdV equation at t = 0.000 shown on Figure 2. It can be readily seen that the nonlinear stage of the MI develops much faster if the initial perturbation contains more spectral modes. For instance, the first initial condition with j = 1 unstable mode shows some signs of the MI. Namely, the cascading modes are already present in the Fourier domain. However, their broadening is not developed yet. It is translated to the physical space by the absence of any amplification of the base wave, while on Figures 2(b,c) the MI is fully developed with amplication factors up to two times.

In order to show that the MI can be fully developed even from a single perturbation mode we present a numerical snapshot on Figure 3 corresponding to the initial condition depicted at Figure 1(a) but taken at the moment of time t = 620.0. A comparable amplification is achieved. However, it happens almost four times slower than for initial conditions shown in Figures 1(b,c).

This series of numerical experiments shows that a broader initial perturbation not only does not suppress the dynamical energy cascade, but also the position of all the cascading modes is not affected. The cascade shape remains exponential and it was studied in details (in the case j = 1) in [START_REF] Dutykh | Direct dynamical energy cascade in the modified KdV equation[END_REF][START_REF] Dutykh | Observation of the Inverse Energy Cascade in the modified Korteweg-de Vries Equation[END_REF]. We performed the same battery of tests for numerous pertubative modes (see Figure 1(b,c)) and with double initial amplitude (thus, double initial wave steepness). In this study we show only one snapshot corresponding to seven spectral modes and the initial amplitude a = 0.16 = 2×0.08. Despite the violent MI observed in this picture (Figure 4, upper panel) the structure of the cascade still can be recognized, even if some deviation from the exponential shape can be recognized.

Double cascade

As it was demonstrated in [START_REF] Dutykh | Observation of the Inverse Energy Cascade in the modified Korteweg-de Vries Equation[END_REF] for the mKdV equation (1.2), a shift in the base mode in Fourier space towards higher frequencies can lead to the formation of a double energy cascade. As in the case of the direct cascade, the experiments were performed with only one unstable mode. In this study we enrich the perturbation with up to seven spectral modes in order to see whether this double cascade can still be observed in such extreme conditions.

The numerical parameters for this series of experiments are provided in Table 2. In the previous work [START_REF] Dutykh | Observation of the Inverse Energy Cascade in the modified Korteweg-de Vries Equation[END_REF] it was notices that the increase in the spectral domain yields the appearance of a second occurrence of the double energy cascade. Consequently, we studied several sizes of the computational spectral domain. Here we report the results for N = 2×16 384 in order to demonstrate the formation of the double cascade along with its repetition in two occurrences if the spectral domain can host them.

The corresponding results are shown on Figure 5 for the initial time t = 0 (panel (a)), t = 5.0 (panel (b)) and the same time t = 160.0 (panel (c)) as in experiments reported above.

As a conclusion, we observe that the double cascade appears almost immediately (see Figure 5(b, lower panel) corresponding to t = 5.0) and it is accompanied by a fully developed MI in the physical space (see Figure 5 results with previous numerical results [START_REF] Dutykh | Observation of the Inverse Energy Cascade in the modified Korteweg-de Vries Equation[END_REF] shows that even the location of cascading modes appears to be the same up to the graphical resolution.

Quartic and quintic gKdV equations

In this Section we will consider the following particular gKdV equations (1.3) where we keep only quartic (α ≡ 0, β ≡ 0, δ > 0, γ ≡ 0) or quintic (α ≡ 0, β ≡ 0, δ ≡ 0, γ > 0) nonlinearities:

quartic KdV(u) ≐ u t + u xxx + δu 3 u x = 0, (3.1)
quintic KdV(u)

≐ u t + u xxx + γu 4 u x = 0. (3.2)
Our main goals are:

• Investigate the existence of the direct and inverse energy cascades • If they exist: -to compare their formation time scales to compare their structure, i.e. the number of cascading modes, their location, spacing, etc.

In order to meet these goals we will take the same numerical set-up as described above for the direct and double cascades correspondingly (see Tables 1 &2). The initial perturbations contain one, four or seven modes as it is shown on Figure 1. Several dozens of computations have been performed for each of two equations (3.1), (3.2). Below we will show the main findings.

Quartic gKdV equation

Direct cascade

The selected results of our numerical simulations are shown on Figure 6 for the initial condition consisting of seven perturbative modes and the base wave amplitude a = 0.08. This choice of parameters comes from the fact that we would like to highlight the differences with the mKdV equation (1.2). The upper pane of Figure 6(a) shows the time moment t = 160.0, while Figure 6(b) reports the system state at t = 3600.0. We can see that during the system evolution new cascading modes appear in the Fourier spectrum tail (high frequencies). The structure and location of peaks remain the same, while their magnitudes can slightly grow with time.

However, there exist an important qualitative difference with the mKdV case reported in the previous Section. Namely, even at t = 160.0 (with all other equal parameters and the initial perturbation) the physical space of the mKdV equation already demonstrates the nonlinear stage of the MI development (see Figures 2(b,c)). On the other hand, the quartic gKdV even for t = 3600.0 (more than twenty times longer!) does not show any signs of the amplification in the physical space (see Figure 6).

In order to show that the nonlinear MI stage does not occur in the quartic gKdV equation, we performed an additional series of the experiments with higher base wave amplitude. On Figure 9(a) we show the physical and Fourier spaces for the case of double initial amplitude a = 2 × 0.08 = 0.16, while on the lower panel Figure 9(b) we show simultaneously Fourier spectra for the simple and double amplitudes at t = 3600.0. As in previous cases, one can see that there is no significant solution amplification in the physical space. Concerning the Fourier space, the superposition shown on Figure 9(b) clearly shows the coincidence of the cascading modes locations, while new high frequency cascading modes appear. We note that the Fourier spectrum shown with red dots contains roughly speaking four times more energy (since the initial amplitude is doubled). However, this extra energy is mainly redistributed towards the appearence of new peaks in the tail of the Fourier spectrum, by conserving the energy of several first cascading modes at the long waves end of the spectrum.

Double cascade

Numerical experiments to study the double energy cascade formation in the quartic gKdV equation were performed similarly to the study of the mKdV equation reported in the previous Section. The main conclusions are the same as for the direct cascade. Namely, in the physical space we do not witness any significant amplification of the base wave.

On the other hand, in the Fourier space several entities of the double cascade are formed. The very interesting fact is that the choice of the spectral domain influences the shape of the double cascade for the quartic gKdV equation. In each spectral domain the total number of cascading modes remains invariant (in the particular case under consideration this number is equal to 19 modes). However, the energy distribution among these modes is different and actually depends on the size of the spectral domain. As we observed in [START_REF] Dutykh | Observation of the Inverse Energy Cascade in the modified Korteweg-de Vries Equation[END_REF], the spectral domain consisting of N = 2 × 16384 Fourier modes can host one entity of the double cascade, while doubling the size of the spectral domain yields logically the appearance of two entities of the cascade (with the total number of cascading modes being 14 in that computation). In order to illustrate this fact for the quartic gKdV equation as well, on Figure 8 we show the formed double cascade for different sizes of the spectral domain.

All pictures are taken at t = 3600.0, even though the location of the modes and the distribution of energy among them is already clearly visible at t = 60.0. Longer simulations are necessary in order to show that we do not observe any nonlinear development of the MI in the physical space on the longer horizon. The effect of the energy redistribution in the spectral domain deserves a separate study. It will be performed elsewhere.

Quintic gKdV equation

The numerical set-up in this Section is precisely the same as above. However, here we focus on the quintic gKdV equation (3.2) with parameter µ = 6.0.

The time evolution under the quintic gKdV equation dynamics (3.2) is totally different from what we observed for the quartic gKdV (3.1). Namely, in the quintic case a well-developed MI can be observed both in Fourier and physical spaces with physical amplifications of the base wave amplitude going up to two times and higher.

On the other hand, these numerical results are qualitatively the same as for the mKdV equation (1.2) reported above and in [START_REF] Dutykh | Direct dynamical energy cascade in the modified KdV equation[END_REF][START_REF] Dutykh | Observation of the Inverse Energy Cascade in the modified Korteweg-de Vries Equation[END_REF]. Namely, the direct and double cascades are accompanied by the nonlinear stage of the MI in the physical space. It can be qualitatively observed on Figure 9(b). An interesting difference with the mKdV consists in the appearance of the instability treshold in the quintic gKdV equation (3.2). Below this supposed instability treshold the quintic gKdV behaves similarly to the quartic gKdV equation in the physical space. It is manifested by the long time dynamics of the modulated solution in the physical space without the development of the nonlinear stage of the MI (see Figure 9(a)). In contrast, when we take the doubled initial base wave amplitude a = 2 × 0.08 = 0.16, the MI in the physical space is well developed already at t = 1200.0 as it can be seen on Figure 9(b).

Concerning the Fourier space, the number of cascading modes, the spacing between them and the shape of the energy spectrum is preserved regardless the base wave amplitude (below or above the instability treshold, see Figure 9). In contrast to the double cascade, the increase in the spectral domain does not lead to the redistribution of the energy among cascading modes. We do not provide the corresponding pictures here. They can be obtained from the authors after a simple request.

For the double cascade in the quintic gKdV we observe the same entities as in the mKdV equation (see Figure 5 and also [START_REF] Dutykh | Observation of the Inverse Energy Cascade in the modified Korteweg-de Vries Equation[END_REF]). However, what is new is the presence of the instability threshold as it was explained for the direct cascade. In order to see the difference the reader can compare Figures 10(a

Discussion

In the present study we investigated several KdV-type equations involving higher order nonlinearities. The main focus was on the formation and properties of the dynamical energy cascade in the Fourier space. The second goal was to describe the cases when the formation of this cascade is accompanied by the nonlinear stage of the MI development in the physical space. This question is of capital importance since the nonlinear stage implies important wave amplifications which are put forward nowadays as one of the main physical mechanisms of the freak wave formation [START_REF] Onorato | Freak waves in random oceanic sea states[END_REF]. Since, the total number of numerical experiments performed in this study exceeded a few hundreds, we included only the most typical ones.

• First of all, we extended the study of the mKdV equation presented in [START_REF] Dutykh | Direct dynamical energy cascade in the modified KdV equation[END_REF][START_REF] Dutykh | Observation of the Inverse Energy Cascade in the modified Korteweg-de Vries Equation[END_REF] for the case of a broader initial perturbation of the base wave. It was found that previous findings can be transposed to this case as well: formation of the direct and double cascades, their structure is preserved and appears to be quite stable. However, in the broad perturbation case all nonlinear processes are accelerated (i.e. they develop in shorter times). • Not only the general structure of the energy cascade is preserved, but also the number of the cascading modes (for the fixed spectral domain and the base wave amplitude) and their location in the Fourier space. • The main difference between the direct and double cascades consists in the fact that the change of the size of the spectral domain does not induce the energy redistribution in the direct cascade, while it changes completely the number of entities, and thus the energy distribution, in the double cascade(s). • In all the mKdV cases, the formation of dynamical cascades is accompanied by the nonlinear stage of the MI development and the substantial amplification of the base wave in the physical space. • In the case of the quartic gKdV equation, all the results about the dynamical cascades formation in the spectral domain remain the same. However, no amplification of the base wave amplitude was observed in the physical space. • The quintic gKdV case is mostly similar to the mKdV equation (with positive nonlinearity) except for the presence of the amplitude threshold in the physical space, below which the amplification does not occur on the time horizons investigated in this study. However, if the amplitude is taken above this threshold, the base wave amplification occurs on longer time scales (virtually three times slower than in mKdV for the parameters considered in this study).

The main findings are summarized in a compact form in Table 3.

Strictly speaking the theory of the dynamical energy cascade [START_REF] Kartashova | Energy transport in weakly nonlinear wave systems with narrow frequency band excitation[END_REF][START_REF] Dutykh | Direct dynamical energy cascade in the modified KdV equation[END_REF] as well as the model equations considered above are valid at best only for moderate nonlinearities ε ∼ O(10 -1 ). However, one can ask a legitimate question: what happens if we push the nonlinearity in the wave system to the finite size ∼ O(1) as in the strong turbulence? For this purpose we performed an additional experiment for the quartic KdV equation (3.1) with the base wave amplitude a = 10 × 0.08 = 0.8. Together with seven perturbative modes the initial condition reaches ε ∼ O(1) announced above. Two numerical snapshots are shown on Figure 11. First of all, one can notice that there is no visible difference between t = 20.0 depicted on the upper panel and t = 100.0 shown below. It means that the fully developed quasi-stationary stage is reached on times T ∼ O(1). However, most surprisingly even for such a strong nonlinearity one can still recognise the presence of the direct dynamic energy cascade, despite the fact that we step out from all reasonnable ranges of model and theory applicability.

Figure 1 .

 1 Figure 1. The same initial condition subject to the different number of perturbation modes.

Figure 2 .

 2 Figure 2. Evolution of the initial conditions shown on Figure at the same time instance t = 160.0.

2 Figure 3 . 2 Figure 4 . 2 (Figure 5 .

 232425 Figure 3. Development of the nonlinear stage of the MI from one unstable mode. This snapshot is taken at t = 620.0.

2 (b) t = 3600. 0 Figure 6 .

 206 Figure 6. Direct cascade in the quartic KdV equation (3.1) with seven perturbative modes for the base wave amplitude a = 0.08.

Figure 7 .

 7 Figure 7. Upper panel (a): Direct cascade in the quartic KdV equation (3.1) with seven perturbative modes for the base wave amplitude a = 0.16 Lower panel (b): Comparison of Fourier spectra obtained for the quartic KdV equation (3.1) with seven perturbation modes at t = 3600.0. Base wave amplitude is a = 0.08 (black dots) and a = 0.16 (red dots).

2 (Figure 8 .

 28 Figure 8. Double energy cascade in the quartic gKdV equation with base wave amplitude a = 0.08 at t = 3600.0. The spectral domain is increasing from up to down.

  ) and 10(b).

2 ( 16 Figure 9 .

 2169 Figure 9. Direct cascade formation for the quintic gKdV equation (3.2) with µ = 6.0 and seven pertubative modes (see Figure 1(c)). In the upper panel (a) the snapshot is taken at t = 3600.0 and in the lower panel (b) at t = 1200.0.

2 ( 16 Figure 10 .

 21610 Figure 10. Double cascade formation for the quintic gKdV equation (3.2) with µ = 6.0 and seven pertubative modes (see Figure 5(a)). In the upper panel (a) the snapshot is taken at t = 560.0 and in the lower panel (b) at t = 35.0.

2 (b) t = 100. 0 Figure 11 .

 2011 Figure 11. Direct cascade in the quartic KdV equation (3.1) with seven perturbative modes for the base wave amplitude a = 10 × 0.08 = 0.8. Together with perturbation it produces the initial condition of the order of O(1).

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 mKdV equation with broad spectrum initial perturbation . . . . . . . . . . . 2.1 Direct cascade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Double cascade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Quartic and quintic gKdV equations . . . . . . . . . . . . . . . . . . . . . . . 3.1 Quartic gKdV equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Direct cascade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.2 Double cascade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Quintic gKdV equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Table 1 .

 1 Various parameters used in simulations of the direct energy cascade subject to a broad excitation.

	The discretization in

Table 2 .

 2 Various parameters used in simulations of the double energy cascade subject to a broad excitation.

	Base wave amplitude, a	0.08
	Perturbation magnitude, δ	0.05
	Base wavenumber, k 0	35 × 1.884
	Perturbation wavenumber, K 0 0.00785
	Ratio of wavelengths, k 0 K 0	240
	Number of Fourier modes, N 2 × 16 384

Table 3 .

 3 The main conclusions of this study summarized in this table. The sign '-' designates the absence of the corresponding property, while '+' means its presence.

	Property/Model KdV (1.1) mKdV (1.2) quartic gKdV (3.1) quintic gKdV (3.2)
	Nonlinear term	uu x	u 2 u x	u 3 u x	u 4 u x
	MI	-	+	-(?)	+
	Direct cascade	-	+	+	+
	Inverse cascade	-	-	-	-
	Double cascade	-	+	+	+
	Energy redistrib.	-	+	+	+
	MI nonlin. stage (amplif. > 2a) Treshold	--	+ -	--	+ +

Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Acknowledgments

This research has been supported by the Austrian Science Foundation (FWF) under projects P22943-N18 and P24671.

The authors would like to thank Professors Walter Craig (McMaster University, Canada), Roger Grimshaw (University College London, UK) and Efim Pelinovsky (Institute of Applied Physics, Russia) for helpful discussions on the topics of the present study.