David Coudert

Guillaume Ducoffe

On the recognition of C 4 -free and 1/2-hyperbolic graphs *

Keywords: Hyperbolicity, algorithm, graph, C 4 -free Hyperbolicité, algorithme, graphe, cycles induit

The shortest-path metric d of a connected graph G is 1 2 -hyperbolic if, and only if, it satisfies d(u, v) + d(x, y) ≤ max{d(u, x) + d(v, y), d(u, y) + d(v, x)} + 1, for every 4-tuple u, x, v, y of G. 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 constant-factor 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 lineartime reduction from the C 4 -free graph recognition problem to the recognition of 1 2 -hyperbolic graphs (Section 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 (Section 3.2). In Section 4, we finally reduce both problems to the problem of the rectangular matrix product that was defined in [START_REF] Gall | 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 Section 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] Bandelt | 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 1. 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: 1 is an isometric subgraph of G.

Condition 1. Every cycle of length at least 6 in G is bridged. Condition 2. For every pair u, v ∈ G, N (u) ∩ [u, v] is a clique. Condition 3. No graph in Figure
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 2. 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 2. 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 2 and Problem 1, one can observe that the condition of Fact 2 is equivalent to Condition 2 when considering vertices u, v at distance 2. As a consequence, every 1 2 -hyperbolic 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 Section 4.1 for details). We will improve this result in Section 4.

The subcubic equivalence

It is straightforward by the definitions that both the 1 2 -hyperbolic graph recognition problem (Problem 1), and the C 4 -free graph recognition problem (Problem 2), 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:

• the reduction runs in Õ(n 3-ε )-time 2 , where n denotes the size of the input;

• 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 subcubictime 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 1 and Problem 2 are subcubic equivalent. We first present a linear-time reduction from Problem 2 to Problem 1 in Section 3.1 (Proposition 3). Then we present a subcubic reduction from Problem 1 to Problem 2 in Section 3.2 (Theorem 14). Proof. Let G = (V, E) be an instance of the C 4 -free graph recognition problem. Let u / ∈ V , and let

Reducing the detection of a C 4 to the recognition of a 1 2 -hyperbolic graph

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 1. We can prove that it always satisfies Condition 3 in the same way. Finally, since Condition 2 is satisfied for every pair u, v ∈ V of adjacent vertices, then G ′ satisfies Condition 2 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 2. 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 2 to Problem 1 here is linear-time, whereas the converse reduction from Problem 1 to Problem 2, presented in Section 3.2, is superlinear. It might be of interest to determine whether a linear-time reduction from Problem 1 to Problem 2 exists.

Finding quadrangles to recognize non-1 2 -hyperbolic graphs

Our aim is now to prove that there exists a subcubic reduction from Problem 1 to Problem 2 (Theorem 14). Ideally, we would ask for a subcubic-time routine for checking whether Conditions 1, 2 and 3 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 1, 2 and 3, 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 1 is satisfied. We recall that Condition 1 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 1, 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 half-integer δ 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: [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.

Lemma 4 ( [9,
• There exists an algorithm computing a 2-factor approximation of the hyperbolicity in O(n

3-ω(1)
2

) = O(n 2.69 )-time [START_REF] Fournier | Computing the gromov hyperbolicity of a discrete metric space[END_REF].

• 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].

• There exists an algorithm computing a 1569-factor approximation of the hyperbolicity in O(min{nm, n ω(1) log n} + n 2 ) = Õ(n 2.3727 )-time3 [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 5 ( [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 5 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 6. 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 5, 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 5, 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 6 implies that every isometric cycle must have length upper-bounded by 5 i.e., Condition 1. 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 7. 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, 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].

E i = {{u, v} : 0 < d G (u, v) ≤ i}.
Recall that we said in Section 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 8. 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 ∈ N G i (u) ∩ N G i (v). It follows by Definition 7 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.
As a consequence, we have by Definition 1 that:

δ(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 8 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 9. 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:

• if ε = 0: d G (u, x) = d G (u, y) = d G (v, x) = d G (u, y) = p; • if ε = 1: d G (u, x) = d G (u, y) = d G (v, x) = p, and d G (v, y) = p + 1; • if ε = 2: d G (u, x) = d G (v, y) = p, and d G (u, y) = d G (v, x) = p + 1; • 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 upperbounded 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 7, 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, that is: 2p + ε 2 -1 -p + ε 4 = p + ε 2 - ε 4 -1 ≥ 0.
A straightforward calculation shows that:

ε 2 - ε 4 = 0 if ε = 1 -1 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 9 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 5.

Transforming some obstructions into quadrangles

One of the most fundamental step for our reduction was to prove with Lemma 8 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 6. 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 6, 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 construction of the graph G [2] .

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 10. Let G = (V, E) be a connected graph. The graph G [2] = (V [2] , E [2] ) is defined as follows:

• V [2] ≃ V × {0, 1}; • G [2] [V × {0}] ≃ G; • G [2] [V × {1}] ≃ G 3 ;
• ∀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] .

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 11. 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. If a, b, c, d ∈ V × {0}
, then there is an induced C 4 in G by Definition 10. Similarly, if a, b, c, d ∈ V × {1}, then there is an induced C 4 in G 3 by Definition 10. In both cases, this implies that G is not 1 2 -hyperbolic, by Lemma 8. 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. Figure 5: Possible quadrangles in G [2] . Weights on the edges represent distances in G.

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.

Recall that in order to decide whether a graph is 1 2 -hyperbolic, our aim is to check whether all of the three Conditions 1, 2 and 3 of [START_REF] Bandelt | 1-hyperbolic graphs[END_REF] are satisfied, using stronger necessary conditions.

Inria

So far, we only dealt with Condition 1, developing tools in Sections 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 10 with the graph powers of Definition 7, in order to ensure that both Conditions 2 and 3 are satisfied as well.

Let us start with Condition 2:

Lemma 12. Let G = (V, E) be a δ-hyperbolic graph, for some δ ≥ 1 2 . Suppose G does not satisfy Condition 2. 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. andd(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.

Proof. Let u, v ∈ V be such that N (u) ∩ [u, v] is not a clique,
• 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:

-d(u, x 1 ) = d(u, y 1 ) = 1; -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 ) = ji, 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 ) = j -i. 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.

Also, note that for all i, δ(u, v, x i , y i ) = d(xi,yi)

2
and so, we have that for every i:

d(x i , y i ) ≤ 2δ.
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:

• d(x 1 , x l ) = d(y 1 , y l ) = l -1; • d(x 1 , y 1 ), d(x l , y l ) ≤ l -1; • d(x 1 , y l ), d(x l , y 1 ) > l -1.
Consequently, x 1 , y 1 , x l , y l are the vertices of an induced quadrangle in G l-1 .

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

Let us finally prove with Lemma 13 that we can verify whether Condition 3 is satisfied in the same way as we verified Condition 2 in Lemma 12.

Lemma 13. Let G = (V, E) be a connected graph that does not satisfy Condition 3. 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 3, 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,

x) = 1, d(u, y) = d(v, x) = 2, d(u, v) = d(x, y) = d(v, y) = 3.
So, (u, 0), (y, 1), (v, 1), (x, 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 8, 9, 11, 12 and 13, the following new characterization of 1 2 -hyperbolic graphs: Characterization 1. A connected graph G is 1 2 -hyperbolic if, 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 8 and 11, and it is sufficient by Lemmas 9, 12 and 13.

Inria 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 16 ([12, 25, 31, 38]). 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 2. There are two main steps of computation in our algorithm, that are described below.

Fact 17 ([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 18. 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 17, 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)}|.

Inria

Combining Fact 17 and Lemma 18, we can now rely on Fact 2 in order to detect, to count and to output induced quadrangles in the graph as follows.

Proposition 19. 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 quadratictime. 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 18, 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 16.

By Fact 2, 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 17 and Lemma 18. 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 18), 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 Section 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.

Figure 1 :

 1 Figure 1: The six forbidden isometric subgraphs.

Proposition 3 .Figure 2 :

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

Figure 3 :

 3 Figure 3: Shrinking long isometric cycles into quadrangles.

2 Figure 4 :

 24 Figure4: The construction of the graph G[2] .

RR n°8458

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

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

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 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]). Inria

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].

[START_REF] Boguñá | Sustaining the Internet with hyperbolic mapping[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.RR n°8458

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgments

We would 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).

The reduction

Theorem 14. 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 4, and two others ones are discussed in Section 3.2.1. 6 . In the sequel, let δ c (G) be a c-factor approximation of the hyperbolicity. Recall that we have δ

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 6, 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

This can be done in subcubic-time, 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 8. If so, then by Lemma 9, there is no isometric cycle C l of length 6 ≤ l ≤ 4δ c (G) + 3. Consequently, the graph G satisfies Condition 1. Finally, let us build G [2] , which can also be done in subcubic-time using the distance-matrix of G. By Lemma 11, 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:

• G [2] and all of G i , 1 ≤ i ≤ 2δ c (G) are C 4 -free, hence G satisfies Condition 2 by Lemma 12;

• G [2] and the square graph G 2 are both C 4 -free and so, G satisfies Condition 3 by Lemma 13.

Thus we can conclude by [START_REF] Bandelt | 1-hyperbolic graphs[END_REF] that G is a 1 2 -hyperbolic graph. Corollary 15. 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 1 and Problem 2 by the subcubic equivalence of Corollary 15. While the algorithm proposed in [START_REF] Spinrad | Finding large holes[END_REF] relies on transitive orientation, our algorithm merely reduces the whole Problem 2 to a fast rectangular matrix multiplication.

A quick reminding of the problem of matrix multiplication is given in Section 4.1, before we present our algorithm to detect an induced quadrangle in Section 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 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 upperbound 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.