Pierre Bergé
email: pierre.berge@uca.fr

Guillaume Ducoffe

Michel Habib

Subquadratic-time Algorithm for the Diameter and all Eccentricities on Median Graphs

Keywords: Median graphs, Diameter, Eccentricities, Hypercubes

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

Introduction

Median graphs can be certainly identified as the most important family of graphs in metric graph theory. Indeed, they are related to numerous areas: universal algebra [START_REF] Avann | Metric ternary distributive semi-lattices[END_REF][START_REF] Birkhoff | A ternary operation in distributive lattices[END_REF], CAT(0) cube complexes [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF][START_REF] Chepoi | Graphs of some CAT(0) complexes[END_REF], abstract models of concurrency [START_REF] Barthélemy | Median graphs, parallelism and posets[END_REF][START_REF] Sassone | A classification of models for concurrency[END_REF], and genetics [START_REF] Bandelt | The fingerprint of phantom mutations in mitochondrial dna data[END_REF][START_REF] Bandelt | Mitochondrial portraits of human populations using median networks[END_REF]. Let d(a, b) be the length (i.e. number of edges) of the shortest (a, b)-path for a, b ∈ V and I(a, b) be the set made up of all vertices u metrically between a and b, i.e. d(a, b) = d(a, u)+d(u, b). Median graphs are the graphs such that for any triplet of distinct vertices x, y, z ∈ V , the intersection I(x, y) ∩ I(y, z) ∩ I(z, x) is a singleton, containing the median of this triplet, denoted by m(x, y, z).

The purpose of this article is to break the quadratic barrier for the computation time of certain metric parameters on median graphs. In particular, we focus on one of the most fundamental problems in algorithmic graph theory related to distances: the diameter. Given an undirected graph G = (V, E), the diameter is the maximum distance d(u, v) for all u, v ∈ V . Two vertices at maximum distance form a diametral pair. An even more general problem consists in determining all eccentricities of the graph. The eccentricity ecc(v) of a vertex v is the maximum length of a shortest path starting from v: ecc(v) = max w∈V d(v, w). The diameter is thus the maximum eccentricity.

State of the art

Executing a Breadth First Search (BFS) from each vertex of an input graph G suffices to obtain its eccentricities in O(n|E|), with n = |V |. As median graphs are relatively sparse, |E| ≤ n log n, these multiple BFSs compute all eccentricities in time O(n 2 log n) for this class of graphs. Very efficient algorithms determining the diameter already exist on other classes of graphs, for example [START_REF] Abboud | Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs[END_REF][START_REF] Cabello | Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs[END_REF][START_REF] Ducoffe | Diameter, eccentricities and distance oracle computations on H -minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension[END_REF]. Many works have also been devoted to approximation algorithms for this parameter. Chechik et al. [START_REF] Chechik | Better approximation algorithms for the graph diameter[END_REF] showed that the diameter can be approximated within a factor 3 2 in time Õ(m are in Θ 0 if they are opposite in a common 4-cycle. A Θ-class is an equivalence class of Θ. Each Θ-class of a median graph forms a matching cutset, splitting the graph into two convex connected components, called halfspaces. The number q ≤ n of Θ-classes corresponds to the dimension of the hypercube in which the median graph G isometrically embeds. Value q satisfies the Euler-type formula 2n -m -q ≤ 2 [START_REF] Klavzar | An Euler-type formula for median graphs[END_REF]. A recent LexBFS-based algorithm [START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF] identifies the Θ-classes in linear time O(|E|) = O(dn). Two subquadratic-time algorithms have been proposed for the recognition of median graphs. Using convex characterizations of halfspaces, Hagauer et al. [START_REF] Hagauer | Recognizing median graphs in subquadratic time[END_REF] showed that median graphs can be recognized in O(n 3 2 log n). In [START_REF] Imrich | Median graphs and triangle-free graphs[END_REF], a bijection between median and triangle-free graphs makes the recognition algorithms for triangle-free graphs work on median ones [START_REF] Alon | Finding and counting given length cycles[END_REF]. Hence, median graphs can be recognized in O((n log 2 n) 1.41 ) using this reduction.

There exist efficient algorithms for some metric parameters on median graphs. For example, the median set and the Wiener index can be determined in O(|E|) [START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF]. Subfamilies of median graphs have also been studied. There is an algorithm computing the diameter and the radius in linear time for squaregraphs [START_REF] Chepoi | Center and diameter problems in plane triangulations and quadrangulations[END_REF]. A more recent contribution introduces a quasilinear time algorithm -running in O(n log O(1) n) -for the diameter on cube-free median graphs [START_REF] Ducoffe | Isometric embeddings in trees and their use in distance problems[END_REF], using distance and routing labeling schemes proposed in [START_REF] Chepoi | Distance labeling schemes for cubefree median graphs[END_REF]. Eventually, a linear-time algorithm [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF] for the diameter on constant-dimension median graphs was proposed, i.e. for median graphs satisfying d = O [START_REF] Avann | Metric ternary distributive semi-lattices[END_REF].

The existence of a truly subquadratic-time algorithm for the diameter on all median graphs is open and was recently formulated in [START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF][START_REF] Ducoffe | Isometric embeddings in trees and their use in distance problems[END_REF]. An even more ambitious question can be asked. Can this subquadratic barrier be overpassed for the problem of finding all eccentricities of a median graph ? As the total size of the output is linear and this problem generalizes the diameter one, this question is legitimate. More generally, the question holds for all metric parameters (except the median set and the Wiener index for which a lineartime algorithm was recently designed). In this article, we propose the first subquadratic-time algorithm computing all eccentricities on median graphs.

Contributions

Our first contribution in this paper is the design of a quasilinear, i.e. O((log n) O(1) n), time algorithm computing the diameter of simplex graphs. A simplex graph K(G) = (V K , E K ) of a graph G is obtained by considering the induced complete graphs (cliques) of G as vertices V K . Then, two of these cliques are connected by an edge if they differ by only one element: one is C, the other is C ∪ {v}. These edges form the set E K . All simplex graphs are median [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF][START_REF] Barthélemy | On the use of ordered sets in problems of comparison and consensus of classifications[END_REF]. Moreover, we observe that simplex graphs admit an interesting property: they admit a central vertex -representing the empty clique -and every Θ-class has an edge incident to that vertex (Lemma 13, Section 3.1).

We describe the algorithm in a few words. We observed that the eccentricities of each vertex of a simplex graph could be written as functions of the size of certain sets of pairwise orthogonal Θ-classes (POFs). Based on that property, we considered an ordering of the POFs based on their cardinality and execute partition refinements. This reveals us a tree structure of the POFs from which the eccentricity of each vertex can be extracted.

First, this algorithm extends the set of median graphs for which a quasilinear time procedure computing the diameter exists. Indeed, simplex graphs form a sub-class of median graphs containing instances with unbounded dimension d.

• There is a combinatorial algorithm determining the diameter and all eccentricities of simplex graphs in O((d 3 + log n)n): Corollary 1, Section 3.2.

Second, we remark that this method can be integrated to the algorithm already proposed in [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF] to compute all eccentricities of median graphs in time O(2 O(d log d) n). This allows us to decrease this running time. Thanks to this modification, the new algorithm proposed computes all eccentricities of a median graph in Õ(2 2d n), where notation Õ neglects poly-logarithmic factors. Even if the algorithm stays linear for constant-dimension median graphs, observe that the dependence on d decreases, from a slightly super-exponential function to a simple exponential one.

• There is a combinatorial algorithm determining all eccentricities of median graphs in Õ(2 2d n): Theorem 9, Section 4.1.

The second and main contribution in this paper is the design of a subquadratic-time dynamic programming procedure which computes all eccentricities of any median graph. Here, the linear simple-exponential-FPT algorithm for all eccentricities presented above plays a crucial role.: it is the base case. This framework consists in partitioning recursively the input graph G into the halfspaces of its largest Θ-class. With our construction, the leaves of this recursive tree are median graphs with dimension at most 1 3 log n and we can apply the former linear-time FPT algorithm.

• There is a combinatorial algorithm determining all eccentricities of median graphs in Õ(n

3 ): Theorem 10, Section 4.2.

We terminate the article with some improvements of the framework we designed. We focus on the computation of all reach centralities [START_REF] Gutman | Reach-based routing: A new approach to shortest path algorithms optimized for road networks[END_REF] in a median graph. The reach centrality of a vertex u is the maximum value min {d(s, u), d(u, t)} over all pairs s, t satisfying u ∈ I(s, t). A linear simple-exponential-FPT algorithm is proposed, as for eccentricities.

• There is a combinatorial algorithm determining all reach centralities of median graphs in Õ(2 3d n): Theorem 12, Section 5.1.

Furthermore, we define a new discrete structure on median graphs: the maximal outgoing POFs (MOPs), generalizing the POFs used throughout the paper and defined in [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]. We propose an alternative procedure to compute all eccentricities, based on the enumeration of MOPs. Furthermore, the MOPs admit an interesting property: for median graphs with "large" d, their number is subquadratic. This provides us with a better subquadratic-time algorithm for the eccentricities using the following win-win approach: either the dimension d of the input graph G is "small" and the linear FPT algorithm is executed fast, or the dimension is "large", then the MOPs can be enumerated fast and our new procedure ensures a smaller runtime.

• There is a combinatorial algorithm determining all eccentricities in Õ(n β ), where β = 1.6456: Theorem 16, Section 5.2.

All these outcomes put in evidence a relationship between the design of linear-time FPT algorithms and the design of subquadratic-time algorithms determining metric parameters on median graphs. We believe that the ideas proposed to establish all these results represent interesting tools to break the subquadratic barrier on other open questions.

Organization

In Section 2, we recall the definition of median graphs. The well-known properties and concepts related to them are listed, among them Θ-classes, signature, and POFs. Section 3 is utterly dedicated to simplex graphs: we establish some characterizations of these graphs and we present our quasilinear-time algorithm determining their eccentricities. In Section 4, we show how to obtain a linear simple-exponential-FPT algorithm for all eccentricities of a median graph, parameterized by the dimension d. Thanks to it, we propose a dynamic programming procedure to transform the computation of eccentricities of any median graph into a sequence of constant-dimension cases. In Section 5, we extend the results obtained so far. We present a linear simple-exponential-FPT algorithm computing all reach centralities of a median graph, parameterized by d. Moreover, we define the notion of MOPs, provide an upper bound of their cardinality and show the impact of this bound on the time complexity on the algorithms proposed earlier. Eventually, we conclude in Section 6 and give some directions of research which could follow the contributions of this article.

Median graphs

In this section, we recall some notions related to distances in graphs, and more particularly median graphs. Two important tools are presented: the Θ-classes, which are equivalences classes over the edge set, and the Pairwise Orthogonal Families (POFs) characterizing Θ-classes belonging to a common hypercube.

Θ-classes

All graphs G = (V, E) considered in this paper are undirected, unweighted, simple, finite and connected. We denote by N (u) the open neighborhood of u ∈ V , i.e. the set of vertices adjacent to u in G. We extend it naturally: for Observe that certain well-known families of graphs are median: trees, grids, squaregraphs [START_REF] Bandelt | Combinatorics and geometry of finite and infinite squaregraphs[END_REF], and hypercubes Q k . Median graphs are bipartite and do not contain an induced K 2,3 [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF][START_REF] Mulder | The structure of median graphs[END_REF][START_REF] Hammack | Handbook of Product Graphs[END_REF]. They can be obtained by Mulder's convex expansion [START_REF] Mulder | The structure of median graphs[END_REF][START_REF] Mulder | The interval function of a graph[END_REF] starting from a single vertex. In other words, G admits Q d as an induced subgraph, but not Q d+1 . Median graphs with d = 1 are exactly the trees. Median graphs with d ≤ 2 are called cube-free median graphs.

Figure 1 presents three examples of median graphs. (a) is a tree: d = 1. (b) is a cube-free median graph: it has dimension d = 2. To be more precise, it is a squaregraph [START_REF] Bandelt | Combinatorics and geometry of finite and infinite squaregraphs[END_REF], which is a sub-family of cube-free median graphs. The last one (c) is a 4-cube: it has dimension d = 4.

We provide a list of properties satisfied by median graphs. In particular, we define the notion of Θ-classes which is a key ingredient of several existing algorithms [START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF][START_REF] Hagauer | Recognizing median graphs in subquadratic time[END_REF][START_REF] Imrich | Median graphs and triangle-free graphs[END_REF].

In general graphs, all gated subgraphs are convex. The reverse is true in median graphs.

Lemma 1 (Convex⇔Gated [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF][START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF]) Any convex subgraph of a median graph is gated.

To improve readibility, edges (u, v) ∈ E are sometimes denoted by uv. We recall the notion of Θ-class, which is well explained in [START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF], and enumerate some properties related to it. We say that the edges uv and xy are in relation Θ 0 if they form a square uvyx, where uv and xy are opposite edges. Then, Θ refers to the reflexive and transitive closure of relation Θ 0 . Let q be the number of equivalence classes obtained with this relation. The classes of the equivalence relation Θ are denoted by E 1 , . . . , E q . Concretely, two edges uv and u ′ v ′ belong to the same Θ-class if there is a sequence uv = u 0 v 0 , u 1 v 1 , . . . , u r v r = u ′ v ′ such that u i v i and u i+1 v i+1 are opposite edges of a square. We denote by E the set of Θ-classes: E = {E 1 , . . . , E q }. To avoid confusions, let us highlight that parameter q is different from the dimension d: for example, on trees, d = 1 whereas q = n -1. Moreover, the dimension d is at most ⌊log n⌋ in general.

Lemma 2 (Θ-classes in linear time [START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF]) There exists an algorithm which computes the Θ-classes E 1 , . . . , Eq of a median graph in linear time O(|E|) = O(dn).

In median graphs, each class E i , 1 ≤ i ≤ q, is a perfect matching cutset and its two sides H ′ i and H ′′ i satisfy nice properties, that are presented below.

Lemma 3 (Halfspaces of E i [START_REF] Mulder | The interval function of a graph[END_REF][START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF][START_REF] Hagauer | Recognizing median graphs in subquadratic time[END_REF]) For any 1 ≤ i ≤ q, the graph G deprived of edges of E i , i.e. G\E i = (V, E\E i ), has two connected components H ′ i and H ′′ i , called halfspaces. Edges of E i form a matching: they have no endpoint in common. Halfspaces satisfy the following properties.

• Both H ′ i and H ′′ i are convex/gated. Subquadratic-time algorithm for the diameter on median graphs

• If uv is an edge of E i with u ∈ H ′ i and v ∈ H ′′ i , then H ′ i = W (u, v) = {x ∈ V : d(x, u) < d(x, v)} and H ′′ i = W (v, u) = {x ∈ V : d(x, v) < d(x, u)}. H ′ i H ′′ i = ∂H ′′ i ∂H ′ i E i Fig. 2: A class E i with sets H ′ i , H ′′ i , ∂H ′ i , ∂H ′′ i
We denote by ∂H ′ i the subset of H ′ i containing the vertices which are adjacent to a vertex in

H ′′ i : ∂H ′ i = N (H ′′ i ) Put differently, the set ∂H ′ i is made up of vertices of H ′ i which are endpoints of edges in E i . Symmetrically, set ∂H ′′ i contains the vertices of H ′′ i which are adjacent to H ′ i .
We say these sets are the boundaries of halfspaces H ′ i and H ′′ i respectively. Figure 2 illustrates the notions of Θ-class, halfspace and boundary on a small example. In this particular case, an halfspace is equal to its boundary:

∂H ′′ i = H ′′ i . The vertices of ∂H ′ i are colored in blue.
Lemma 4 (Boundaries [START_REF] Mulder | The interval function of a graph[END_REF][START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF][START_REF] Hagauer | Recognizing median graphs in subquadratic time[END_REF]) Both ∂H ′ i and ∂H ′′ i are convex/gated. Moreover, the edges of E i define an isomorphism between ∂H ′ i and ∂H ′′ i .

As a consequence, suppose uv and u ′ v ′ belong to E i : if uu ′ is an edge and belongs to class E j , then vv ′ is an edge too and it belongs to E j . We terminate this list of lemmas with a last property dealing with the orientation of edges from a canonical basepoint v 0 ∈ V . The v 0 -orientation of the edges of G according to v 0 is such that, for any edge uv, the orientation is

# » uv if d(v 0 , u) < d(v 0 , v). Indeed, we cannot have d(v 0 , u) = d(v 0 , v) as G is bipartite. The v 0 -orientation is acyclic.
Lemma 5 (Orientation [START_REF] Bénéteau | Medians in median graphs and their cube complexes in linear time[END_REF]) All edges can be oriented according to any canonical basepoint v 0 .

From now on, we suppose that an arbitrary basepoint v 0 ∈ V has been selected and we refer automatically to the v 0 -orientation when we mention incoming or outgoing edges.

Shortest paths and signature

We fix an arbitrary canonical basepoint v 0 and for each class E i , we say that the halfspace containing v 0 is H ′ i . Given two vertices u, v ∈ V , we define the set which contains the Θ-classes separating u from v.

Definition 2 (Signature σu,v) We say that the signature of the pair of vertices u, v, denoted by σu,v, is the set of classes E i such that u and v are separated in G\E i . In other words, u and v are in different halfspaces of E i .

The signatures of two vertices provide us with the composition of any shortest (u, v)-path. Indeed, all shortest (u, v)-paths contain exactly one edge for each class in σ u,v . Lemma 6 ([26]) For any shortest (u, v)-path P , the edges in P belong to classes in σu,v and, for any E i ∈ σu,v, there is exactly one edge of E i in path P . Conversely, a path containing at most one edge of each Θ-class is a shortest path between its departure and its arrival.

This result is a direct consequence of the convexity of halfspaces. By contradiction, a shortest path that would pass through two edges of some Θ-class E i would escape temporarily from an halfspace, say w.l.o.g H ′ i , which is convex (Lemma 3).

Definition 2 can be generalized: given a set of edges B ⊆ E, its signature is the set of Θ-classes represented in that set: {E i : uv ∈ E i ∩ B}. The signature of a path is the set of classes which have at least one edge in this path. In this way, the signature σ u,v is also the signature of any shortest (u, v)-path. The signature of a hypercube is the set of Θ-classes represented in its edges: the cardinality of the signature is thus equal to the dimension of the hypercube.

Orthogonal Θ-classes and hypercubes

We present now another important notion on median graphs: orthogonality. In [START_REF] Kovse | Complexity of phylogenetic networks: counting cubes in median graphs and related problems[END_REF], Kovse studied a relationship between splits which refer to the halfspaces of Θ-classes. It says that two splits Indeed, classes E i and E j are orthogonal if and only if the splits produced by their halfspaces are incompatible.

{H ′ i , H ′′ i } and H ′ j , H ′′ j are incompatible if the four sets H ′ i ∩ H ′ j , H ′′ i ∩ H ′ j , H ′ i ∩ H ′′ j ,
Lemma 7 (Orthogonal⇔Incompatible [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]) Given two Θ-classes E i and E j of a median graph G, the following statements are equivalent:

• Classes E i and E j are orthogonal,

• Splits {H ′ i , H ′′ i } and H ′ j , H ′′ j are incompatible, • The four sets ∂H ′ i ∩ ∂H ′ j , ∂H ′′ i ∩ ∂H ′ j , ∂H ′ i ∩ ∂H ′′ j , and
∂H ′′ i ∩ ∂H ′′ j are nonempty.
The concept of orthogonality is sometimes described with different words in the literature depending on the context: incompatible, concurrent or crossing. We say that E i and E j are parallel if they are not orthogonal, that is

H i ⊆ H j for some H i ∈ {H ′ i , H ′′ i } and H j ∈ H ′ j , H ′′ j .
We pursue with a property on orthogonal Θ-classes: if two edges of two orthogonal classes E i and E j are incident, they belong to a common square.

Lemma 8 (Squares [START_REF] Barthélemy | Median graphs, parallelism and posets[END_REF][START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]) Let xu ∈ E i and uy ∈ E j . If E i and E j are orthogonal, then there is a vertex v such that uyvx is a square.

Pairwise orthogonal families. We focus on the set of Θ-classes which are pairwise orthogonal.

Definition 4 (Pairwise Orthogonal Family) We say that a set of classes X ⊆ E is a Pairwise Orthogonal Family (POF for short) if for any pair E j , E h ∈ X, we have

E j ⊥ E h .
The empty set is considered as a POF. We denote by L the set of POFs of the median graph G. The notion of POF is strongly related to the induced hypercubes in median graphs. First, observe that all Θ-classes of a median graph form a POF if and only if the graph is a hypercube of dimension log n [START_REF] Kovse | Complexity of phylogenetic networks: counting cubes in median graphs and related problems[END_REF][START_REF] Mcmorris | The median procedure on median graphs[END_REF]. Secondly, the next lemma makes precise the relationship between POFs and hypercubes.

Lemma 9 (POFs adjacent to a vertex [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]) Let X be a POF, v ∈ V , and assume that for each E i ∈ X, there is an edge of E i adjacent to v. There exists a hypercube Q containing vertex v and all edges of X adjacent to v. Moreover, the Θ-classes of the edges of Q are the classes of X.

There is a natural bijection between the vertices of a median graph and the POFs. The next lemma exhibits this relationship.

Lemma 10 (POFs and hypercubes [START_REF] Bandelt | The fingerprint of phantom mutations in mitochondrial dna data[END_REF][START_REF] Kovse | Complexity of phylogenetic networks: counting cubes in median graphs and related problems[END_REF][START_REF] Bandelt | Combinatorics of lopsided sets[END_REF]) Consider an arbitrary canonical basepoint v 0 ∈ V and the v 0 -orientation for the median graph G. Given a vertex v ∈ V , let N -(v) be the set of edges going into v according to the v 0 -orientation. Let E -(v) be the classes of the edges in N -(v). The following propositions are true:

• For any vertex v ∈ V , E -(v) is a POF. Moreover, vertex v and the edges of N -(v) belong to an induced hypercube formed by the classes E -(v). Hence,

|E -(v)| = |N -(v)| ≤ d. • For any POF X, there is an unique vertex v X such that E -(v X ) = X. Vertex v X is the closest-to-v 0 vertex v such that X ⊆ E -(v). • The number of POFs in G is equal to the number n of vertices: n = |L|. E 1 E 2 E 3 E 4 v 0 v 1 v 2 v 3 v 4 v 5 v 6 v 7 Vertex v 0 v 1 v 2 v 3 POF ∅ {E 3 } {E 1 } {E 1 , E 3 } Vertex v 4 v 5 v 6 v 7 POF {E 4 } {E 2 } {E 2 , E 3 } {E 2 , E 4 }
Fig. 3: Illustration of the bijection between V and the set of POFs.

An example is given in Figure 3 with a small median graph of dimension d = 2. v 0 is the canonical basepoint and edges are colored according to their Θclass. For example, v 1 v 3 ∈ E 1 . We associate with any POF X of G the vertex v X satisfying E -(v X ) = X with the v 0 -orientation. Obviously, the empty POF is associated with v 0 which has no incoming edges.

A straightforward consequence of this bijection is that parameter q, the number of Θ-classes, is less than the number of vertices n. But it can be used less trivially to enumerate the POFs of a median graph in linear time [START_REF] Bandelt | The fingerprint of phantom mutations in mitochondrial dna data[END_REF][START_REF] Kovse | Complexity of phylogenetic networks: counting cubes in median graphs and related problems[END_REF]. Given a basepoint v 0 , we say that the basis (resp. anti-basis) of an induced hypercube Q is the single vertex v such that all edges of the hypercube adjacent to v are outgoing from (resp. incoming into) v. Said differently, the basis of Q is its closest-to-v 0 vertex and its anti-basis is its farthest-to-v 0 vertex. What Lemma 10 states is also that we can associate with any POF X a hypercube Q X which contains exactly the classes X and admits v X as its anti-basis. This observation implies that the number of POFs is less than the number of hypercubes in G. Moreover, the hypercube Q X is the closest-to-v 0 hypercube formed with the classes in X. Figure 4a shows a vertex v with its incoming and outgoing edges with the v 0 -orientation. The dashed edges represent the hypercube with anti-basis v and POF E -(v).

Number of hypercubes. We recall a formula establishing a relationship between the number of POFs and the number of hypercubes in the literature.

E i E j E h v (a)
The hypercube "induced" by the edges incoming into a vertex (its antibasis). Let α(G) (resp. β(G)) be the number of hypercubes (resp. POFs) in G. Let β i (G) be the number of POFs of cardinality i ≤ d in G. According to [START_REF] Bandelt | The fingerprint of phantom mutations in mitochondrial dna data[END_REF][START_REF] Kovse | Complexity of phylogenetic networks: counting cubes in median graphs and related problems[END_REF], we have:

E i E h E j ∂H ′′ i ∩ ∂H ′′ j v ′ v Q ′ Q (b) A POF signing at least two hyper- cubes Q and Q ′ is not maximal.
α(G) = d i=0 2 i β i (G) (1)
Equation ( 1) produces a natural upper bound for the number of hypercubes. Value α(G) considers all hypercubes, in particular those of dimension 0, i.e. vertices. From now on, the word "hypercube" refers to the hypercubes of dimension at least one.

Each hypercube in the median graph G can be defined with only its anti-basis v and the edges N of the hypercube that are adjacent and going into v according to the v 0 -orientation. These edges are a subset of N -(v): N ⊆ N -(v). Conversely, given a vertex v, each subset of N -(v) produces a hypercube which admits v as an anti-basis (this hypercube is a sub-hypercube of the one obtained with v and N -(v), Lemma 10). Another possible bijection is to consider a hypercube as a pair composed of its anti-basis v and the Θ-classes E of the edges in N (its signature).

As a consequence, a simple graph search such as BFS enables us to enumerate the hypercubes in G in time O(d2 d n).

Lemma 12 (Enumeration of hypercubes [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]) We can enumerate all triplets (v, u, E), where v is the anti-basis of a hypercube Q, u its basis, and E the signature of Q in time O(d2 d n). Moreover, the list obtained fulfils the following partial order: if

d(v 0 , v) < d(v 0 , v ′ ), then any triplet (v, u, E) containing v appears before any triplet (v ′ , u ′ , E ′ ) containing v ′ .
The enumeration of hypercubes is thus executed in linear time for median graphs with constant dimension. In summary, given any median graph, one can compute the set of Θ-classes and their orthogonality relationship (for each E i , the set of Θ-classes orthogonal to E i ) in linear time, and the set of hypercubes with its basis, anti-basis and signature in Õ(2 d n).

Maximal POFs. We terminate this preliminary section with a few words on maximal POFs, i.e. POFs X such that there is no other POF Y ⊋ X.

There is a natural bijection between maximal POFs and maximal hypercubes, put in evidence by the following result.

Theorem 1 (Maximal POFs and hypercubes) For any maximal hypercube, its signature is a maximal POF. Conversely, for any maximal POF X, there exists a unique hypercube of signature X. Its anti-basis is the vertex v such that E -(v) = X.

Proof Let Q be a maximal hypercube and X Q its signature. We begin with the proof that

X Q is a maximal POF. Assume that Y ⊋ X Q . As Y is a POF, there is a vertex v Y ∈ V satisfying E -(v Y ) = Y . Similarly, we denote by v X the vertex such that E -(v X ) = X Q . Both v X and v Y belong to the boundary of any Θ-class of X Q (the one which is the farthest from v 0 ). In brief, v X , v Y ∈ Ei∈X Q ∂H ′′ i (2)
As every ∂H ′′ i is gated, then the intersection written in Eq. ( 2) is convex/gated too. Thus, the shortest (v X , v Y )-path is entirely contained in set X Q ∂H ′′ i . Let (v X , z) be the first edge of this path and E j the Θ-class of this edge. Each Θ-class form an isomorphism between its two boundaries (Lemma 4): as z ∈ X Q ∂H ′′ i , there is a hypercube isomorphic to Q in the boundary of E j containing z. Therefore, there is a hypercube of dimension |X Q | + 1 containing all vertices of Q. This yields a contradiction as Q is supposed to be maximal.

Conversely, let Q be a hypercube and assume that its signature X Q is a maximal POF. We suppose that there is a second hypercube

Q ′ ̸ = Q such that X Q = X Q ′ .
Then, the set X Q ∂H ′′ i contains at least two elements: the anti-bases of hypercubes Q and Q ′ . Using the same argument as above, we can put in evidence an edge with two endpoints in X Q ∂H ′′ i . The Θ-class of this edge is thus orthogonal of any class E i of X Q which defines an isomorphism between ∂H ′ i and ∂H ′′ i . Consequently, we obtain a POF superset of X Q , a contradiction.

For any POF X, there is at least one hypercube with signature X such that its anti-basis v verifies E -(v) = X according to Lemma 10. In summary, any maximal POF X can be associated with an unique hypercube of signature X. □ Figure 4b illustrates this proof with two squares Q and Q ′ with the same signature {E i , E h }. One can observe the appearance of a hypercube of larger dimension containing Q, giving evidence of the non-maximality of X Q .

The number of maximal hypercubes in a median graph is thus equal to the number of maximal POFs, which is itself at most linear in the number of vertices.

Simplex graphs

In this section, we present a combinatorial algorithm computing the diameter and all eccentricities of simplex graphs in quasilinear time, i.e. in O((d 3 + log n)n). We begin with some properties of these graphs and then describe the algorithm.

Simplex and crossing graphs: cliques, diameter and opposites

Given any undirected graph G, the vertices of the simplex graph K(G) associated to G represent the induced cliques (not necessarily maximal) of G. Two of these cliques are connected by an edge if they differ by exactly one element.

Definition 5 (Simplex graphs [START_REF] Bandelt | Embedding topological median algebras in products of dendrons[END_REF]) The simplex graph

K(G) = (V K , E K ) of G = (V, E) is made up of the vertex set V K = {C ⊆ V : C induced complete graph of G} and the edge set E K = (C, C ′ ) : C, C ′ ∈ V K , C ⊊ C ′ , |C ′ | -|C| = 1 .
Observe that the empty clique of G also corresponds to a vertex v ∅ in K(G). Therefore v ∅ has degree n = |V | in K(G). Figure 5 shows, as an example, the simplex graph of a C 5 . Labels indicate the correspondence between vertices and cliques. We note that simplex graphs of cycles are cogwheels, i.e. wheels with a subdivision on each external edge.

The simplex graph of a n-complete graph is a hypercube of dimension n. More generally, simplex graphs are median [START_REF] Bandelt | Metric graph theory and geometry: a survey[END_REF][START_REF] Barthélemy | On the use of ordered sets in problems of comparison and consensus of classifications[END_REF]. We will see later than certain median graphs are not simplex graphs. As a subfamily of median graphs, the design of a subquadratic-time algorithm for the eccentricities on simplex graphs is of interest. Moreover, the dimension d of simplex graphs can be unbounded because hypercubes belong to this class of graphs (their dimension is logarithmic in the size of the vertex set). Simplex graphs can be characterized as particular median graphs.

Theorem 2 Let G be a median graph. The following statements are equivalent:

(1) G is a simplex graph.

(2) There is a vertex

v 0 ∈ V (G) such that each Θ-class of G is adjacent to v 0 , i.e. ∀1 ≤ i ≤ q, ∃v i ∈ V (G), v 0 v i ∈ E i .
(3) There is a vertex v 0 ∈ V (G) contained in any maximal hypercube of G.

Proof (2)⇔(3). Assume each Θ-class is adjacent to v 0 . For each POF X, there is a hypercube with signature X and containing v 0 (Lemma 9). For each maximal hypercube, its signature (the set of Θ-classes it contains) is a maximal POF and, moreover, no other maximal hypercube has the same signature (Theorem 1). For this reason, each maximal hypercube necessarily contains v 0 . Conversely, if any maximal hypercube contains v 0 , as each Θ-class belongs to at least one maximal POF, then each Θ-class is necessarily adjacent to v 0 .

(2)⇒(1). We consider a median graph G such that all Θ-classes are adjacent to v 0 . Our objective is to prove that there exists G ′ such that G = K(G ′ ). Let G ′ be the graph where its vertices represent the Θ-classes of G and two of them are connected by an edge if the Θ-classes are orthogonal. In this way, every clique of G ′ (even the empty one) corresponds to a POF of G. For any POF X of G, its Θclasses are adjacent to v 0 , so there exists a hypercube containing v 0 with signature X, according to Lemma 9. Moreover, given a POF X, this hypercube is unique. Its anti-basis (opposite of v 0 ) thus represents the clique X in G ′ . Conversely, according to the v 0 -orientation, each vertex admits its own set of incoming Θ-classes which forms a POF (Lemma 10). Therefore, we can associate to each vertex of G a clique of G ′ .

Then, two vertices u, v of G are adjacent if and only if

E -(v) = E -(u) ∪ {E i }, for some class E i . On one hand, suppose uv ∈ E i . Assume that there exists E j ∈ E -(u)\E -(v). Then, E j is parallel to E i , otherwise E j ∈ E -(v) (Lemma 8
). This is a contradiction: as

H ′′ i ⊊ H ′′ j , E i cannot be adjacent to v 0 . Moreover, if E h ∈ E -(v)\E -(u), h ̸ = i, then E h is necessarily incoming into u because of Lemma 8, as E h and E i are orthogonal. So, E -(v)\E -(u) = {E i }. On the other hand, if E -(v) = E -(u) ∪ {E i }, let v ′ be the vertex such that v ′ v ∈ E i . Again, Lemma 8 implies that all Θ-classes incoming into v are also incoming into v ′ , so E -(u) ⊆ E -(v ′ ). Furthermore, if there is some E j / ∈ E -(u) incoming into v ′ , then it should be parallel to E i , a contradiction. Hence, v ′ = u.
(1)⇒( 2). Assume that G = K(G ′ ): we denote by v ∅ the vertex representing the empty clique. By contradiction, we suppose that there exists a Θ-class which is not adjacent to v ∅ : we denote it by E 1 . We consider the v ∅ -orientation of the graph. As {E 1 } is a POF, there is necessarily one vertex v 1 with only one incoming edge belonging to

E 1 . As v 1 ̸ = v ∅ , vertex v 1 represents a clique of G ′ of size at least 1. If v 1
represents a clique of size exactly 1, then it is adjacent to v ∅ because only one element differ between the cliques represented by both v ∅ and v 1 , which is a contradiction. If v 1 represents a clique of size at least 2, then it has at least two incoming edges. another contradiction. In summary, if

G = K(G ′ ), each Θ-class of G is adjacent to v ∅ . □
In this section only, on simplex graphs, the canonical basepoint v 0 is not selected arbitrarily. We fix v 0 as a vertex adjacent to all Θ-classes, as put in evidence by Theorem 2. We call v 0 the central vertex of the simplex graph.

What Theorem 2 says is that any simplex graph can be seen as a set of maximal POFs (or hypercubes) that are "medianly" assembled. Indeed, one cannot define a simplex graph given any collection of sets -excluding subsets -representing maximal POFs. Consider as an example the collection {{E 1 , E 2 } , {E 2 , E 3 } , {E 3 , E 1 }}: it would produce a simplex graph with 3 squares with basis v 0 and sharing pairwise an edge. This graph is Q - 3 (the 3cube minus a vertex) and is not median. The collection implies that E 1 , E 2 , E 3 are pairwise orthogonal, so {E 1 , E 2 , E 3 } should be the maximal POF here.

The most obvious example of median graph which is not simplex is certainly the path P 4 . Indeed, it has three Θ-classes which are all pairwise parallel. For any vertex of P 4 , there exists a Θ-class which is not adjacent to it.

The proof (2)⇒(1) reveals the reverse application of K.

Definition 6 (Crossing graphs [START_REF] Bandelt | Embedding topological median algebras in products of dendrons[END_REF][START_REF] Klavzar | Partial cubes and crossing graphs[END_REF]) Let G be a median graph. Its crossing graph G # is the graph obtained by considering Θ-classes as its vertices and such that two Θ-classes are adjacent if they are orthogonal.

Restricted to simplex graphs, this transformation is the reverse of K: indeed, as stated in [START_REF] Klavzar | Partial cubes and crossing graphs[END_REF], G = K(G) # . The clique number of G # is exactly the dimension of median graph G. For example, the crossing graph of a cubefree median graph contains no triangle. Each simplex graph admits a central vertex (v 0 in Theorem 2) which represents the empty clique of G # . Now, we focus on the problem of determining a diametral pair of a simplex graph G and more generally all eccentricities. Observe that the distance between the central vertex v 0 and any vertex u of G can be deduced directly from the edges incoming into u. We state that σ v0,u = E -(u). This is a consequence of Theorem 2: all Θ-classes of E -(u) are adjacent to v 0 , so v 0 is the basis of the hypercube with signature E -(u) and anti-basis u. A shortest (v 0 , u)-path is thus made up of edges of this hypercube. The distance d(v 0 , u) is equal to its dimension:

d(v 0 , u) = |E -(u)|.
A key result is the fact that the central vertex v 0 of the simplex graph belongs to the interval I(u, v) of any pair u, v satisfying d(u, v) = ecc(u).

Lemma 13 Let u, v ∈ V (G) such that d(u, v) = ecc(u). Then, v 0 ∈ I(u, v). Proof Let H be the graph such that G = K(H). The distance d(u, v) is equal to the number of Θ-classes of G separating them, so d(u, v) = |E -(u)△E -(v)|. Let w be the vertex of G such that E -(w) = E -(v)\E -(u). If E -(u) ∩ E -(v) ̸ = ∅, then d(u, w) = |E -(u) △ E -(w)| = |E -(u)| + |E -(w)| > |E -(u)\E -(v)| + |E -(v)\E -(u)| = d(u, v). So, d(u, w) > ecc(u), a contradiction. □ E i v 0 m u v
w Fig. 6: Illustration of the contradiction in the proof of Lemma 13.

Figure 6 shows a simple example with m = m(u, v, v 0 ) ̸ = v 0 and d(v 0 , m) = 1. The edges are oriented according to the v 0 -orientation. The Θ-class E i in σ v0,m is present alongside the interval I(m, v). The contradiction of the previous proof comes from the fact that the shortest (u, v)-path could be extended with the vertex w which is the neighbor of v in ∂H ′ i . Two vertices u, v forming a diametral pair cannot share a common incoming

Θ-class E i , in other words E -(u) ∩ E -(v) = ∅, otherwise m = m(u, v, v 0 ) ∈ I(u, v) ⊆ H ′′ i and v 0 ∈ H ′ i . Moreover, the distance d(u, v) is exactly |E -(u)| + |E -(v)| because |E -(u)| = d(v 0 , u) and |E -(v)| = d(v 0 , v). So, determining the diameter of a simplex graph G is equivalent to maximizing the sum |X| + |Y |,
where X and Y are two POFs of G that are disjoint. Computing the diameter is equivalent to finding the largest pair of disjoint cliques in the crossing graph G # . Similarly, the eccentricity of a vertex u is exactly the size

|E -(u)|+|E -(v)| of the largest pair of disjoint POFs (E -(u), E -(v)
). Now, we can define the notion of opposite.

Definition 7 Let G be a simplex graph and X a POF of G. We denote by op(X) the opposite of X, i.e. the POF Y disjoint from X with the maximum cardinality.

op(X) = argmax Y ∩X=∅ |Y |.
With this definition, the eccentricity of a vertex u, if we fix

X u = E -(u), is written ecc(u) = |X u | + |op(X u )|.
Hence, the diameter of the simplex graph G can be written as the size of the largest pair POF-opposite:

diam(G) = max X∈L (|X| + |op(X)|).
We propose now the definition of two problems on simplex graphs. The first one, called Opposites (OPP) consists in finding all pairs POF-opposite. Its output has thus a linear size. Given the solution of OPP on graph G, one can deduce both the diameter and all eccentricities in O(n) time with the formulae presented above.

Definition 8 (OPP)

Input: Simplex graph G, central vertex v 0 . Output: For each POF X, its opposite op(X).

We define an even larger version of the problem where a positive integer weight is associated with each POF. We call it Weighted Opposites (WOPP).

Definition 9 (WOPP)

Input:

Simplex graph G, central vertex v 0 , weight function ω : L → N + . Output: For each POF X, its weighted opposite Y maximizing ω(Y ) such that X ∩ Y = ∅.
Obviously, OPP is a special case of WOPP when ω is the cardinality function. In Section 3.2, we show that WOPP can be solved in quasilinear time O((d 3 + log n)n). As a consequence, all eccentricities of a simplex graph G can also be determined with such time complexity. Moreover, we will see in Section 4 that solving WOPP in quasilinear time implies that all eccentricities of any median graph can be computed with a simple exponential time 2 O(d) n, improving the slightly super-exponential time proposed in [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF].

Quasilinear algorithm for all eccentricities in simplex graphs

We propose an algorithm solving WOPP in quasilinear time Õ(n).

Theorem 3 There is a combinatorial algorithm solving WOPP in time O((

d 3 + log n)n).
Thus, we can compute the diameter and all eccentricities of simplex graphs in quasilinear time, even when the dimension is not bounded.

Corollary 1 There is a combinatorial algorithm determining all eccentricities of a simplex graph in time O((

d 3 + log n)n).
The entire subsection is the proof of Theorem 3. We consider a simplex graph G with a central vertex v 0 and a weight function ω : L → N + . The algorithm is presented in Sections 3.2.1 and 3.2.2 and its analysis in Section 3.2.3.

Tree structure of the opposites

The first step of our algorithm consists in building a binary tree T . Tree T is a representation of a partition refinement procedure over L. We remind the reader that partition refinement is a powerful algorithmic technique leading to the design of linear-time algorithms for many well-known problems [START_REF] Habib | Partition refinement techniques: An interesting algorithmic tool kit[END_REF][START_REF] Paige | Three partition refinement algorithms[END_REF]. It consists in successive partitionings of a collection of sets.

In our context, the collection which is splitted is the set of POFs L of the simplex graph G. The vertices a ∈ V (T ) of tree T , called nodes, represent the sets obtained from the successive partitionings. They are indexed with POFs L a ∈ L. The edges of T are indexed with a pair class-boolean. For each a ∈ V (T ) with two children, the two edges connecting it to its children are both indexed with the same Θ-class but not the same boolean. This Θ-class is denoted by E [a]. To improve the readibility, index (E [a] , true) will be denoted by +E

[a] while (E [a] , false) becomes -E [a].
We denote by L [E i ] the adjacency list of Θ-class E i , i.e. the list of POFs in L which contain E i . As at most d classes belong to any POF, the total size of all adjacency lists is upper-bounded by dn = d|L|.

We sort the POFs in L in function of their weights ω(L) in the decreasing order. This takes O(n log n). We denote by τ ω this ordering. Let L 0 be the maximum-weighted POF in L, in other words the first POF in ordering τ ω .

The description of the construction of T by partition refinement begins. We assign an arbitrary ordering to the Θ-classes which are in L 0 , for example based on their index. Let E i1 , E i2 , . . . , E ir be the classes of L 0 ordered, |L 0 | = r. First, we split L in two sets: one with POFs containing E i1 , the other with POFs which do not contain E i1 . In brief, we obtain L [E i1 ] and its complementary. Second, we split each of these two sets regarding Θ-class E i2 : on one side the POFs containing E i2 , on the other side POFs without E i2 . We pursue in this way with all classes of L 0 . At the end, there are at most 2 |L0| sets in the partition.

Until now, we obtained the top r levels of tree T . Before pursuing the construction, we define some notations. Let a 0 be the root of T . Node a 0 represents the entire collection L. Let Ω be the function indicating the sets represented by each node a ∈ V (T ). We have Ω(a 0 ) = L. For any a ∈ T , its index L a is defined as the maximum-weighted POF of its universe Ω(a). So, L a0 = L 0 . The root a 0 has two children, one representing L [E i1 ] and the other one its complementary as they are the result of a partition refinement from E i1 . The edges connecting a 0 and its children are indexed by +E i1 and -E i1 respectively.

We denote by R(a) the set of Θ-classes we can find on the simple path from a to the root a 0 . For example, for node a with an universe Ω(a) being the set of POFs which contain We pursue the construction of T . For each leaf a of the current tree, we execute the following process: we only consider the Θ-classes of L a which have not been treated earlier, i.e. which are not in R + (a). We order them arbitrarily and we split the universe Ω(a) successively. We pursue with the new leaves obtained, etc. In this way, tree T can be seen as a stacking of small binary trees (depth at most d) that we call blocks. For example, the root a 0 of T belongs to the top block which is produced from the partition refinement over Θ-classes of L 0 . In Figure 7a, we represent some nodes a of this block and their index L a with |L 0 | = 3: i 1 = i, i 2 = j, and i 3 = ℓ. The leaves of this block both belong to the top block and are the roots of another block below this one. Fig. 7: An example of tree T : its first block and structure Algorithm 1 provides us with the pseudocode of a partition refinement procedure. We call it Ordered Internal Partition Refinement (OIPR). We execute OIPR to obtain tree T with the following input: the ground set contains the Θ-classes of G (W = E), the collection is made up of the POFs outgoing from m with the v 0 -orientation (S = L) and the ordering of the sets come from the POFs weights (τ = τ ω ). Each while loop (line 4) corresponds to the construction of a block of T . Such step starts by picking up the first element, say L a , of a non-singleton set of P, say Ω(a). Then, we consider the Θ-classes of L a which have not been locally visited, i.e. which do not belong to R + (a) (line 7). For each of these classes E j , we refine the non-singleton Ω(a): we split it successively with the POFs containing E j and the POFs not containing E j (line 8).

E i2 but not E i1 , we have R(a) = {E i1 , E i2 }. We write R(a) = R + (a) ∪ R -(
{E i , E j , E ℓ } {E j , E ℓ , E q } {E j , E ℓ , E q } {E j , E r } a 0 a 1 a 2 a 3 -E i +E i -E j +E j +E ℓ -E ℓ (a)
1: Input: ground set W = {w 1 , . . . , w q }, collection S = {S 1 , . . . , S N }, S i ⊆ W for any 1 ≤ i ≤ N , and an ordering τ of S. 2: Output: An ordered partition P of S made up of singletons. 3: Initialize P ← {S}, partition with a single set; 4: while there exists a part of P which is not a singleton do 5:

Q ← first non-singleton of the ordered partition P; 6:

A ← first element of Q according to τ ; 7:

for every w j ∈ A non locally visited do 8:

Substitute Q in P by Refine(Q, {w j }); 9:

endfor end Algorithm 1: Ordered Internal Partition Refinement (OIPR)
The time needed to run Algorithm 1, using a doubly linked list data structure, depends on the number of appearances of each element w j of the ground set into the collection S.

Lemma 14 (Execution time of OIPR [START_REF] Habib | Partition refinement techniques: An interesting algorithmic tool kit[END_REF]) Let M (w j ) be the number of sets S i ∈ S such that w j ∈ S i . Then, OIPR runs in O( q j=1 M (w j )).

In our context, values M (w j ) are the sizes of adjacency lists L [E j ]. We explained above why the total size of these adjacency lists could not exceed dn. Proof The time needed to sort all POFs according to their weights, i.e. in order τω, is O(n log n). Moreover, OIPR runs in O(dn) according to Lemma 14. □

Each set obtained from a refinement is represented by a node of T . Its children are obtained from a refinement of Ω(a) with some Θ-class E j = E [a]: one represents the elements of Ω(a) containing E j (the edge from a to this child is indexed with +E j ), the other represents the complementary (the edge from a to this child is indexed with -E j ). Now, we give some notations and properties related to the tree T . At least one partitioning is executed at each depth of tree T so, as L is finite, T is too. Its depth is at most n = |L|. We say the layer of a node a is the number of blocks we pass through when we traverse the simple path between the root and a minus 1. For example, the root has layer 0 and the leaves of the top block have layer 1. We denote by T (j) , j ≥ 1, the subtree of T induced on the set made up of (i) nodes of layer at most j -1 and (ii) nodes of layer j which are the roots of a block. In this way, nodes of layer j in T (j) are leaves. The depth of T (j) is at most jd, as the depth of each block is at most d.

Certain nodes a ∈ V (T ) may admit only one child. This situation occurs when E [a] is not orthogonal to at least one class of R + (a). Indeed, each POF of Ω(a) contains all Θ-classes of R + (a

): if R + (a) ∪ {E [a]} is not a POF, then there is no POF superset of R + (a) ∪ {E [a]}.
For any node a, we store its universe Ω(a). With the doubly linked list data structure for each partitioning, we can preserve the original ordering of the POFs. Consequently, in all sets Ω(a), the POFs are sorted in function of their weight. For any a ∈ V (T ), the maximum-weighted POF of Ω(a), i.e. index L a , is thus obtained with constant running time.

Even if the execution time of OIPR is quasilinear in n, the extra time needed to store the tree T and particularly all sets Ω(a) may not be linear in n.

In the remainder, we will see that considering tree T (d) suffices to solving our problem. In this way, storing T (d) becomes quasilinear in n, like the execution of the partitioning.

Constraint pairs

The second step of our algorithm uses a data structure called constraint pair, whose definition is based on tree T . We provide a dynamic programming (DP) algorithm which computes one value per constraint pair. At the end of the execution, we can deduce the opposite of each POF in O(1).

Definition 10 (Constraint pair) A constraint pair (a, X) is made up of a node a ∈ V (T ) and a POF X such that (i) X ∩ R(a) = ∅ and (ii) X ∪ R + (a) ∈ L.
The existence of a constraint pair (a, X) implies that no class of X is present in the edge indices from a 0 to a in T . Moreover, each Θ-class of X is orthogonal to all Θ-classes of R + (a). We denote by C the set of constraint pairs. Let C (j) be the set of constraint pairs (a, X) such that a ∈ T (j) : we have

C (j) ⊆ C (j+1) ⊆ C.
For any constraint pair (a, X), we denote by h(a, X) a POF X * disjoint from X in Ω(a) with the maximum weight. For any POF L ∈ L, the POF h(a 0 , L) is an opposite of L because Ω(a 0 ) = L, so we can write, according to Definition 7, h(a 0 , L) = op(L). Observe that any pair (a 0 , L) is a constraint pair as R(a 0 ) = ∅. We present a method to compute all opposites h(a 0 , L).

The description of the DP algorithm starts. For any constraint pair (a, X), we denote by a + (resp. a -) the child of a which is the endpoint of the edge indexed with +E [a] (resp. -E [a]) in T (Figure 8). We define the set C(a, X) which describes the recursive calls needed to compute h(a, X). Formally, the objective is to make sure that value h(a, X) is exactly a function of all h(a ′ , X ′ ), where (a ′ , X ′ ) ∈ C(a, X). The construction of set C(a, X) is described below. We distinguish four cases: A, B, C, and D.

Ω(a), L a , R(a) Ω(a -), L a -, R(a -) Ω(a + ), L a + , R(a + ) a a - a + -E [a] +E [a]
Fig. 8: Nodes a, a + and a -in tree T .

• Case A. No class of X is in L a , i.e. L a ∩ X = ∅. Otherwise, see next cases.
As L a is the maximum-weighted POF in Ω(a) and

L a ∩ X = ∅, we have h(a, X) = L a . No recursive call is needed: C(a, X) = ∅.
A special case of Case A is when Ω(a) is a singleton: Ω(a) = R + (a). We know from Definition 10 that R + (a) ∩ X = ∅.

• Case B. Class E [a] belongs to X: E [a] ∈ X. Otherwise, see next cases. As R(a -) = R(a) ∪ {E [a]}, (a -, X\(E [a])) is a constraint pair (Defini- tion 10): R(a -) ∩ (X\(E [a])) = ∅ and R + (a -) = R + (a) is orthogonal to all Θ-classes of set X\(E [a]) ⊊ X. We fix C(a, X) as a singleton containing (a -, X\(E [a])): C(a, X) = {(a -, X\(E [a]))}. • Case C. Set E [a] ∪ X is a POF: E [a] ∪ X ∈ L. As E [a] / ∈ X, we have X ∩ R(a + ) = X ∩ R(a -) = ∅. First, R + (a -) = R + (a), so X ∪ R + (a -) is a POF and (a -, X) ∈ C. Second, R + (a + ) = R + (a) ∪ E [a]: as E [a] is orthogonal to all Θ-classes of X, R + (a + ) ∪ X is a POF and (a + , X) ∈ C. These two constraint pairs are the elements of C(a, X): C(a, X) = {(a + , X), (a -, X)}. • Case D. Set E [a] ∪ X is not a POF: E [a] ∪ X / ∈ L. Let X |E[a] ⊊ X be the Θ-classes of X which are orthogonal to E [a]
. Pair (a -, X) is a constraint pair, using the same arguments as in Case C. We verify whether another pair

(a + , X |E[a] ) ∈ C. As X |E[a] ⊊ X and E [a] / ∈ X, we have R(a + ) ∩ X |E[a] = ∅. Furthermore, X |E[a] ∪ R + (a) is a POF because (a, X) is a constraint pair and X |E[a] ∪ E [a] is a POF by definition, so X |E[a] ∪ R + (a + ) is a POF. We fix C(a, X) = (a -, X), (a + , X |E[a] ) .
Observe that when (a ′ , X ′ ) ∈ C(a, X), then a is a parent of a ′ in T . Moreover, X ′ ⊆ X. The size of all sets of recursive calls C(a, X) is at most two. The following theorem justifies that POF h(a, X) can be determined as a function of all h(a ′ , X ′ ) satisfying (a ′ , X ′ ) ∈ C(a, X).

Theorem 4 Let (a, X) ∈ C. If C(a, X) = ∅ (Case A), h(a, X) is equal to La. Otherwise: h(a, X) = argmax h(a ′ ,X ′ ) s.t. (a ′ ,X ′ )∈C(a,X) ω h(a ′ , X ′ ) (3)
Proof The justification for Case A was evoked above: as La ∩ X = ∅ and La is the maximum-weighted POF of Ω(a), then h(a, X) = La.

In Case B, E [a] ∈ X. Recall that C(a, X) = (a -, X\E [a]) in this case. POF h(a, X), which is disjoint from X, cannot contain class E [a].
As a consequence, h(a, X) belongs to Ω(a -) which is made up of the POFs of Ω(a) without

E [a]. Moreover, h(a, X) does not contain any class of X\E [a]. We have: h(a, X) = h(a -, X\E [a]).
In Case C, we assume that E [a]∪X is a POF. As E [a] / ∈ X, h(a, X) can be either in Ω(a -) or in Ω(a + ). POFs h(a -, X) and h(a + , X) are respectively the maximumweighted POFs of Ω(a -) and Ω(a + ) without any class of X. Equation (3) holds as C(a, X) = (a -, X), (a + , X) .

In Case D, we assume that E

[a] ∪ X is not a POF. As in Case C, E [a] / ∈ X, so (a -, X) is a constraint pair. If h(a, X) belongs to Ω(a -), then it is h(a -, X). Moreover, (a + , X |E[a] ) ∈ C and we prove that if h(a, X) belongs to Ω(a + ), it is h(a + , X |E[a] ). Let E h be a Θ-class of X\X |E[a] . Classes E h and E [a] are parallel, otherwise E h would belong to X |E[a]
. All POFs of set Ω(a + ) contain E [a], so none of them can contain E h : it would be contradictory with the non-orthogonality of these Θ-classes. In summary, no POF in Ω(a + ) contains a Θ-class of X\X |E [a] . Therefore, determining the maximum-weighted POF of Ω(a + ) disjoint from X is equivalent to finding the maximum-weighted POF of Ω(a

+ ) disjoint from X |E[a] . In brief, if h(a, X) is in Ω(a + ), it is h(a + , X |E[a] ). Equation (3) holds as C(a, X) = (a -, X), (a + , X |E[a] ) . □
The DP algorithm consists in recursively applying Equation (3) from all h(a 0 , L), for any L ∈ L and store the POFs h(a, X) which are computed throughout the execution. Case A is the base case of the recursion. Let H be the directed acyclic graph (DAG) representing the recursive calls of our DP. Its vertex set V (H) contains all (a, X) ∈ C such that h(a, X) is called for the computation of certain POFs h(a 0 , L). Its edge set is made up of arcs from (a, X) ∈ V (H) to elements in C(a, X). Certain constraint pairs of C may not belong to V (H), i.e. they are not needed to compute the opposites. Figure 9 illustrates the DAG H with a vertex (a, X) and its nearby successors. In this example, pair (a, X) is needed for the computation of op(L) = h(a 0 , L) and op( L) = h(a 0 , L): dotted lines mean there is a path between two pairs. We observe that the constraint pairs of V (H) are made up of nodes of T (d) .

(a 0 , L) (a 0 , L) Proof We proceed by induction. The roots of the DAG, i.e. the constraint pairs (a 0 , X), verify this inequality, as layer(a 0 ) = 0. Assume now that the ancestors of (a, X) ∈ V (H) satisfy the inequality. We distinguish two cases. First, suppose there is a predecessor of (a, X), i.e. a constraint pair (a ′ , X ′ ) and an arc going from it to (a, X), such that layer(a) = layer(a ′ ) + 1. We select a pair ( a ′ , X ′ ) in V (H) which is an ancestor of (a ′ , X ′ ) -there is a directed path from ( a ′ , X ′ ) to (a ′ , X ′ ) in H -and such that a ′ is the ancestor of a ′ in T which is at the top of the block B a ′ of layer layer(a ′ ) containing a ′ . Thus, node a is a leaf of block B a ′ . The existence of a directed path in H from ( a ′ , X ′ ) to (a, X) means that the recursive computation of h( a ′ , X ′ ) uses the term h(a, X). The POF L a ′ is not disjoint from X ′ otherwise pair ( a ′ , X ′ ) would be a leaf in

(a, X) (a ′ , X ′ ) (a ′′ , X ′′ ) (ã, X) C(a, X) C(a ′ , X ′ )
H (Case A). Let E h ∈ L a ′ ∩ X ′ . As a is a leaf of the block B a ′ , it verifies E h ∈ R(a) by construction of T . As ( a ′ , X ′ ) is an ancestor of (a, X), then X ⊆ X ′ . But (a, X) is a constraint pair and E h ∈ R(a), so X ⊆ X ′ \ {E h }. In brief, |X| ≤ | X ′ | -1. Using the induction hypothesis, |X| ≤ d -layer( a ′ ) -1 = d -layer(a).
Second, suppose that all predecessors (a ′ , X ′ ) of (a, X) satisfy layer(a ′ ) = layer(a).

As X ⊆ X ′ , |X| ≤ |X ′ | ≤ d -layer(a ′ ) = d -layer(a). □
As a consequence, for any pair (a, X) ∈ V (H), the depth of node a in T can be upper-bounded by d 2 because each block has at most depth d and the layer of a is at most d. Formally, V (H) ⊆ C (d) . This shows that computing tree T (d) -and getting rid of the larger depths of the tree -is sufficient for the execution of the DP. This observation allows us to state in the next subsubsection that this algorithm runs in quasilinear time.

Analysis

In this section, we prove that the DP algorithm described earlier can run in quasilinear time O(d 3 n). The global algorithm is divided into two parts.

1. Construction of the tree T (d) with maximum layer d, using partition refinement, storage of Ω(a), L a , and R(a) for each node a of T (d) . 2. Computation of all opposites h(a 0 , L) with DP.

The runtime needed to build T (d) is O(d 2 n). The execution time of all partitionings is O((d + log n)n), according to Corollary 2. The memory space used to store sets Ω(a), L a , R(a) for each node a ∈ V (T (d) ) can be upper-bounded by O(d 2 n) because the sets Ω(a) together at some fixed depth form a partition of L and the depth of

T (d) is at most d 2 .
The analysis for the second part of the algorithm is not trivial. Our key argument consists in providing an upper bound for the number of constraint pairs in C (d) . It provides us with a maximum number of POFs which have to be stored during the DP.

Theorem 5 There are at most d 2 n constraint pairs in C (d) .

Proof We define a function f : L → 2 C such that, for any L ∈ L, |f (L)| ≤ d 2 . We show that for any constraint pair (a, X) ∈ C (d) , there is a POF Y , X ⊆ Y , such that (a, X) ∈ f (Y ). As the total number of constraint pairs generated by f is at most

d 2 n, we have |C (d) | ≤ d 2 n.
-Step 1: definition of function f . Our method consists in defining an itinerary function I : C (d) → C (d) , where (a, X) = I(a ′ , X ′ ) implies that X ⊆ X ′ and a is a child of a ′ in T (d) . Starting from some (a 0 , Y ), where Y ∈ L, successive appliances of function I provide us with a descent in T (d) , i.e. a simple path from a 0 to a leaf of T (d) , if we refer to the nodes of the constraint pairs obtained. Function f will be defined as follows: f (Y ) = {(a 0 , Y ), I(a 0 , Y ), I(I(a 0 , Y )), . . .}. As the depth of

T (d) is at most d 2 , we confirm that |f (Y )| ≤ d 2 .
Here is the definition of function I and we verify the properties announced above. Let (a ′ , X ′ ) ∈ C (d) : we denote by a -(resp. a + ) its child which is the endpoint of edge indexed by -E a ′ (resp. +E a ′ ). We distinguish three cases: as they are similar to some Cases enumerated in the previous subsubsection, we denote them by B*, C* and D* respectively.

• Case B*:

Θ-class E [a ′ ] belongs to X, i.e. E [a ′ ] ∈ X. We fix I(a ′ , X ′ ) = (a -, X\ {E [a ′ ]}). • Case C*: E [a ′ ] / ∈ X and E [a ′ ] ∪ X is a POF. We fix I(a ′ , X ′ ) = (a + , X). • Case D*: E [a ′ ] / ∈ X and E [a ′ ]∪X is not a POF. We fix I(a ′ , X ′ ) = (a -, X).
Any constraint pair is concerned by one of these three cases. One can see that if I(a ′ , X ′ ) = (a, X) then a is a child of a ′ and X ⊆ X ′ .

-Step 2: any constraint pair is generated by f . We show that any (a, X) ∈ C (d) can be written as I k (a 0 , Y ) for some POF Y ⊇ X and 0 ≤ k < d 2 . We proceed

B a ′ a 0 I (a 0 , Y ) (a ′ , X ′ ) = I k (a 0 , Y ) (a, X) = I k+1 (a 0 , Y ) a * a ′
a Fig. 10: Nodes a, a ′ , and a * in T when a ′ is not the root of a block in Scenario 1. Blue arrows indicate the successive appliances of the itinerary function on (a 0 , Y ).

by induction on the depth of a. The base case is trivial: If depth(a) = 0, then a = a 0 . For any X ∈ L, (a 0 , X) ∈ f (X).

Let (a, X) ∈ C (d) , a ̸ = a 0 , we assume that each constraint pair containing an ancestor of a belongs to some f (Y ). We distinguish three scenarios depending on the nature of both the parent a ′ of a and Θ-class E a ′ . For each scenario, we show that there is a constraint pair (a ′ , X ′ ) such that I(a ′ , X ′ ) = (a, X) and X ⊆ X ′ . As (a ′ , X ′ ) = I k (a 0 , Y ) and X ′ ⊆ Y by induction, such statement implies that (a, X) = I k+1 (a 0 , Y ) and X ⊆ Y , in other words (a, X) ∈ f (Y ).

• Scenario 1: edge (a ′ , a) in T is indexed by -E [a ′ ] and X ∪ E [a ′ ] is a POF. Let X ′ = X ∪ {E [a ′ ]}.
We begin with the proof that (a ′ , X ′ ) is a constraint pair. First, set R(a) is the union of singleton

{E [a ′ ]} with R(a ′ ), so E [a ′ ] / ∈ R(a ′ ). As (a, X) ∈ C, X ∩ R(a) = ∅, so X ∪ {E [a ′ ]} has no intersection with R(a ′ ). In brief, X ′ ∩ R(a ′ ) = ∅. Second, as (a, X) ∈ C, we affirm that any Θ- class of X is orthogonal to any class of R + (a) = R + (a ′ ). Showing that E [a ′ ] is orthogonal to any class of R + (a ′ ) will imply that X ′ ∪ R + (a ′ ) is a POF. If a ′ is the root of some block, then E [a ′ ] is a Θ-class of L a ′ . As L a ′ contains all Θ-classes of R + (a ′
) by definition, this shows the orthogonality of E [a ′ ] with R + (a ′ ). Now, assume that a ′ is not the root of some block: B a ′ denotes the block it belongs to and the root of B a ′ is written a * ̸ = a ′ (Figure 10). Node a * is an ancestor of a ′ . Set R + (a ′ ) can be splitted as follows: on one hand, the Θ-classes of R + (a ′ ) indexed between a 0 and a * , i.e. R + (a * ), and on the other hand the Θ-classes of R + (a ′ ) whose indices appear in the block B a ′ , i.e. R + (a ′ ) ∩ L a * . Class E [a ′ ] belongs to L a * , otherwise a ′ would be the leaf of this block and, therefore, the root of another block. Both R + (a * ) and

R + (a ′ ) \ R + (a * ) are subsets of L a * , so R + (a ′ ) ⊊ L a * . As a conclusion, R + (a ′ ) ∪ {E [a ′ ]} ⊆ L a * is a POF, therefore X ′ ∪ R + (a ′
) is a POF and (a ′ , X ′ ) is thus a constraint pair. We show that I(a ′ , X ′ ) = (a, X). We refer to Case B*: the Θ-class E [a ′ ] belongs to X ′ , so function I returns (a -, X ′ \ {E [a ′ ]}) = (a, X).

• Scenario 2: edge (a ′ , a) in T is indexed by -E [a ′ ] and X ∪ E [a ′ ] is not a POF. Let X ′ = X. As (a, X) ∈ C and R(a ′ ) ⊊ R(a), we have X ∩ R(a ′ ) = ∅. Moreover, R + (a ′ ) = R + (a), so X ∪ R + (a ′ ) is a POF. In brief, (a ′ , X ′ ) = (a ′ , X) ∈ C.
We prove that I(a ′ , X ′ ) = (a, X). In this scenario, X ∪{E [a ′ ]} is not a POF. Furthermore, X ∩ R(a) = ∅ because (a, X) ∈ C, so E [a ′ ] / ∈ X. We refer to Case D* and I(a ′ , X ′ ) = (a -, X ′ ) = (a, X).

• Scenario 3: edge (a ′ , a) in T is indexed by +E [a ′ ]. Let X ′ = X. As (a, X) ∈ C and R(a ′ ) ⊊ R(a), we have X ∩ R(a ′ ) = ∅ as in Scenario 2. Moreover, R + (a ′ ) ⊊ R + (a): only E [a ′ ] is in R + (a) and not in R + (a ′ ). As X ∪ R + (a) is a POF, its subset X ∪ R + (a ′ ) is too. In brief, (a ′ , X ′ ) = (a ′ , X) ∈ C. We show that I(a ′ , X ′ ) = (a, X). Class E [a ′ ] is not in X ′ = X because X ∩ R(a) = ∅. Set X ∪ {E [a ′ ]} is a subset of the POF X ∪ R + (a) because E [a ′ ] ∈ R + (a), so X ∪ {E [a ′ ]} is a POF. We refer to Case C*: I(a ′ , X ′ ) = (a + , X ′ ) = (a, X).
In summary, there is a constraint pair (a ′ , X ′ ) such that a ′ is the parent of a, X ⊆ X ′ , and I(a ′ , X ′ ) = (a, X). The induction hypothesis terminates the proof of our claim: as (a ′ , X ′ ) is in some itinerary f (Y ) with X ′ ⊆ Y , and I(a ′ , X ′ ) = (a, X), then (a, X) also belongs to f (Y ). As the size of each f (Y ), Y ∈ L is upper-bounded by d 2 , the total number of constraint pairs is at most d 2 n. □

The size of the state space of the DP procedure is at most O(d 3 n) because |h(a, X)| ≤ d for any (a, X) ∈ V (H). For any pair (a, X) ∈ V (H), at most two recursive calls are launched to compute h(a, X). In brief, Theorem 5 allows us to affirm that the execution time of the DP procedure is O((d 3 + log n)n) and is thus the total running time of our algorithm.

Subquadratic-time algorithm for all eccentricities on median graphs

This section is dedicated to the design of algorithms computing all eccentricities for the whole class of median graphs (not only simplex graphs). We begin in Section 4.

Linear FPT algorithm for constant-dimension median graphs

We recall in this subsection the different steps needed to obtain a linear-time algorithm computing all eccentricities of a median graph with constant dimension, d = O(1). We show how the algorithm of Section 3.2 can be integrated to it in order to improve the dependence on d. Let us begin with a reminder of the former result.

Lemma 16 ([26]

) There is a combinatorial algorithm computing all eccentricities in a median graph G with running time Õ(2 d(log d+1) n).

Some parts of this subsection are redundant with [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF], however we keep this subsection self-contained. The new outcomes presented are Theorems 7 and 9. The results that are reminded will also be useful for Section 5.

The algorithm evoked by Lemma 16 consists in the computation of three kinds of labels: ladder labels φ, opposite labels op and anti-ladder labels ψ. The order in which they are given correspond to their respective dependence: oplabelings are functions of labels φ and ψ-labelings are functions of both labels φ and op. The definition of op-labelings on general median graphs is very close to the notion of opposite previously defined for simplex graphs in Section 3.

Ladder labels

Some preliminary work has to be done before giving the definition of labels φ. We introduce the notion of ladder set. It is defined only for pairs of vertices u, v satisfying the condition u ∈ I(v 0 , v). In this situation, the edges of shortest (u, v)-paths are all oriented towards v with the v 0 -orientation. Definition 11 (Ladder set Lu,v) Let u, v ∈ V such that u ∈ I(v 0 , v). The ladder set Lu,v is the subset of σu,v which contains the Θ-classes admitting an edge adjacent to u.

Figure 11 shows a small median graph with four vertices v 0 , u, v, x such that u ∈ I(v 0 , v) and u ∈ I(v 0 , x). It gives the composition of ladder sets L u,v and L u,x .

A key characterization on ladder sets states that their Θ-classes are pairwise orthogonal. In brief, every set L u,v is a POF. Let us recall that the adjacency of all Θ-classes of a POF L with the same vertex u implies the existence of a (unique) hypercube not only signed with this POF L but also containing u (Lemma 9). If additionnally POF L is outgoing from u -said differently, the edges adjacent to u belonging to a Θ-class of L leave u -, then u is the basis of the hypercube. As the Θ-classes of L u,v are adjacent to u by definition, there is a natural bijection between (i) hypercubes (ii) pairs made up of a vertex u and a POF L outgoing from u and (iii) pairs vertex-ladder set (u, L u,• ). The necessary background to introduce labels φ is now known.

E 1 E 2 E 3 E 4 E 5 v 0 u v x Fig. 11: Examples of ladder sets: L u,v = {E 2 , E 3 }, L u,x = {E 1 , E 2 , E 3 }.
Definition 12 (Labels φ [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]) Given a vertex u and a POF L outgoing from u, let φ(u, L) be the maximum distance d(u, v) such that u ∈ I(v 0 , v) and Lu,v = L.

Intuitively, integer φ(u, L) provides us with the maximum length of a shortest path starting from u into "direction" L. Observe that the total size of labels φ on a median graph G does not exceed O(2 d n), according to Lemma 11. We provide another notion related to orthogonality which will be used in the remainder.

Definition 13 (L-parallelism) We say that a POF L ′ is L-parallel if, for any

E j ∈ L ′ , L ∪ E j is not a POF. When L ′ is a L-parallel POF, we have L ∩ L ′ = ∅, otherwise L ∪ {E j } = L
for some E j ∈ L ′ . Presented differently, a L-parallel POF is such that any of its Θ-classes is parallel to at least one Θ-class of L.

A combinatorial algorithm running in Õ(2 2d n) which computes all labels φ(u, L) was identified in [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]: we provide an overview of it. There is a crucial relationship between a label φ(u, L) and the labels of (i) the anti-basis u + of the hypercube with basis u and signature L and (ii) the L-parallel POFs outgoing from u + . Lemma 18 (Inductive formula for labels φ [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]) Let u ∈ V , L be a POF outgoing from u and Q be the hypercube with basis u and signature L. We denote by u + the opposite vertex of u in Q: u is the basis of Q and u + its anti-basis. A vertex v ̸ = u + satisfies u ∈ I(v 0 , v) and Lu,v = L if and only if (i) u + ∈ I(v 0 , v) and (ii) ladder set L u + ,v is L-parallel.

A consequence of the previous lemma is that we can distinguish two cases for the computation of φ(u, L). In the first case, φ(u, L) = |L|: it occurs when the farthest-to-u vertex with ladder set L is u + (base case). Indeed, u + is a candidate as σ u,u + = L: shortest (u, u + )-paths pass through hypercube Q. This situation happens when either no Θ-class is outgoing from u + or when all Θ-classes outgoing from u + are orthogonal to L. In the second case, there are vertices farther to u than u + with ladder set L. As announced in Lemma 18, φ(u, L) is a function of labels φ(u + , •).

φ(u, L) = max L + POF outgoing from u + ∀Ej ∈L + , L∪{Ej } not POF (|L| + φ(u + , L + )). (4)
If there exists such a POF L + , then the label φ(u, L) is given by Equation ( 4). Otherwise, it is given by the first case. Briefly, the algorithm consists in listing all pairs vertex-ladder set ((u, L), (u + , L + )) such that u + is the anti-basis of the hypercube of basis u and signature L. For each of them, we verify whether L + is L-parallel. If it is, we update φ(u, L) if |L|+φ(u + , L + ) is greater than the current value. The total number of pairs ((u, L), (u + , L + )) is upper-bounded by 2 2d n: there are at most 2 d n pairs (u + , L + ) (bijection with hypercubes) and, for each of them, there are at most 2 d compatible pairs (u, L) such that u + is the anti-basis of (u, L). Indeed, the number of edges incoming into u + is at most d (Lemma 10). For this reason, the computation of φ-labelings takes Õ(2 2d n).

Theorem 6 (Computation of labels φ [26]

) There is a combinatorial algorithm which determines all labels φ(u, L) in Õ(2 2d n). It also stores, for each pair (u, L), a vertex v satisfying Lu,v = L and d(u, v) = φ(u, L), denoted by µ(u, L).

Opposite labels

The second type of labels needed to compute all eccentricities of a median graph G are opposite labels. Their definition is very close to the function op defined in Section 3 for simplex graphs. Given a vertex u and a POF L outgoing from u, let op u (L) denote a POF with maximum label φ which is disjoint from L. As for φ, the total size of op-labelings is O(2 d n).

Definition 14 (Labels op [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]) Let u ∈ V and L be a POF outgoing from u. Let op u (L) be one of the POF L ′ outgoing from u, disjoint from L, which maximizes value φ(u, L ′ ).

On simplex graphs, the opposite function provides in fact the op-labelings of vertex v 0 : op(X) = op v0 (X). As all vertices belong to hypercubes with basis v 0 , the ladder set L v0,v for any vertex v ∈ V is exactly the set E -(v) of Θclasses incoming into v. So, value φ(v 0 , X) is the distance d(v 0 , v) between v 0 and the only vertex v with ladder set L v0,v = X.

On general median graphs, the opposite label op u (L) allows us to obtain the maximum distance d(s, t) such that u = m(s, t, v 0 ) and the ladder set L u,s is L.

Lemma 19 (Relationship between medians and disjoint outgoing POFs [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]) Let L, L ′ be two POFs outgoing from a vertex u. Let s (resp. t) be a vertex such that u ∈ I(v 0 , s) (resp. u ∈ I(v 0 , t)) and Lu,s = L (resp. L u,t = L ′ ). Then, u ∈ I(s, t) if and only if L ∩ L ′ = ∅. Therefore, given a single vertex s such that u ∈ I(v 0 , s) and Lu,s = L, the maximum distance d(s, v) we can have with median m(s, v, v 0 ) = u is exactly d(u, s) + φ(u, op u (L)).

Going further, given a vertex u ∈ V , the maximum distance d(s, t) such that u = m(s, t, v 0 ) is the maximum value φ(u, L) + φ(u, op u (L)), where L is POF outgoing from u.

An algorithm was initially proposed to compute all labels op u (L) consisting in a brute force bounded tree search [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]. Its execution time was Õ(2 O(d log d) n), leading to the global same asymptotic running time (Lemma 16) for finding all eccentricities.

Fortunately, the quasilinear time algorithm solving WOPP (Theorem 3, Section 3.2) offers us the opportunity to decrease the exponential term to a simple exponential function 2 d . For any u ∈ V , let G u = G [V u ] be the star graph of u, using a definition from [START_REF] Chepoi | Distance labeling schemes for cubefree median graphs[END_REF]. Its vertex set V u is made up of the vertices belonging to a hypercube with basis u in G. Graph G u is the induced subgraph of G on vertex set V u (see Figure 12 for an example). Chepoi et al. [START_REF] Chepoi | Distance labeling schemes for cubefree median graphs[END_REF] showed that graph G u is a gated/convex subgraph of G. This notion of star graph is essential for the proof of the following key theorem.

Theorem 7 (Computation of labels op) There is a combinatorial algorithm which determines all labels op u (L) in Õ(2 d n).

Proof Let u ∈ V : we denote by Nu the number of hypercubes of G with basis u. Convex subgraphs of median graphs are also median by considering the original definition of median graphs (Definition 1). Consequently, star graph Gu is median and all its maximal hypercubes contain a common vertex u. From Theorem 2, Gu is a simplex graph.

Any pair (u, L) of G, where L is a POF outgoing from u in G, can be associated to a unique hypercube with signature L and basis u. Thus, there is a natural bijection between (i) the POFs of Gu (ii) the vertices of Gu and (iii) the POFs L of G outgoing from u. Hence, |Vu| = Nu.

We associate with any POF L of Gu the weight ωu(L) = φ(u, L). We solve WOPP on graph Gu with weight function ωu, using the algorithm evoked in Theorem 3. The opposite computed with that configuration correspond exactly to the labels op u (L): a POF L ′ disjoint from L and maximizing φ(u, L ′ ) among all POFs outgoing from u. The running time of the algorithm is O((

d 3 + log |Vu|)|Vu|) = O((d 3 + log n)Nu).

Anti-ladder labels

We terminate with anti-ladder labels ψ which play the converse role of ladder labels φ. While φ(u, L) is defined for POFs L outgoing from u, labels ψ(u, R) are defined for POFs R incoming into u, i.e. every Θ-class of the POF has an edge entering u. As any such pair (u, R) can be associated with a hypercube of anti-basis u and signature R (Lemma 10), the total size of ψ-labelings is at most O(2 d n) too.

The notion of milestone intervenes in the definition of labels ψ. We consider two vertices u, v such that u ∈ I(v 0 , v). Milestones are defined recursively.

Definition 15 (Milestones Π(u, v)) Let Lu,v be the ladder set of u, v and u + be the anti-basis of the hypercube with basis u and signature Lu,v. If u + = v, then pair u, v admits two milestones: Π(u, v) = {u, v}. Otherwise, the set Π(u, v) is the union of

Π(u + , v) with vertex u: Π(u, v) = {u} ∪ Π(u + , v).
The milestones are the successive anti-bases of the hypercubes formed by the vertices and ladder sets traversed from u to v. Both vertices u and v are contained in Π(u, v). The first milestone is u, the second is the anti-basis u + of the hypercube with basis u and signature L u,v . The third one is the anti-basis u ++ of the hypercube with basis u + and signature L u + ,v , etc. All milestones are metrically between u and v: Π(u, v) ⊆ I(u, v).

Definition 16 (Penultimate milestone π(u, v)) We say that the milestone in Π(u, v) different from v but the closest to it is called the penultimate milestone. We denote it by π(u, v). Furthermore, we denote by Lu,v the anti-ladder set of u, v, i.e. the Θ-classes of the hypercube with basis π(u, v) and anti-basis v.

L u,v L u + ,v L u ++ ,v v 0 u v u + u ++
Fig. 13: A pair u, v with u ∈ I(v 0 , v) and its milestones Π(u, v) in red.

Figure 13 shows the milestones Π(u, v) = {u, u + , u ++ , v}. The hypercubes with the following pair basis-signature are highlighted with dashed edges: (u, L u,v ), (u + , L u + ,v ), and (u ++ , L u ++ ,v ). We have π(u, v) = u ++ and L u,v = L u ++ ,v is drawn with dashs in purple.

Let R be a POF incoming to some vertex u and u -be the basis of the hypercube with anti-basis u and signature R. Label ψ(u, R) intuitively represents the maximum distance of a shortest path arriving to vertex u from "direction" R.

Definition 17 (Labels ψ [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]) The label ψ(u, R) is the maximum distance d(u, v) we can obtain with a vertex v satisfying the following properties:

• m = m(u, v, v 0 ) ̸ = u, • the anti-ladder set of m, u is R: L m,u = R.
Equivalently, vertex u -is the penultimate milestone of pair m, u: u -= π(m, u).

As for the computation of labels φ, there is an induction process to determine all ψ(u, R). As the base case, suppose that u -= v 0 . The largest distance d(u, v) we can obtain with a vertex v such that v 0 ∈ I(u, v) consists in considering the opposite op v0 (R) of R which is outgoing from v 0 . Hence,

ψ(u, R) = |R| + φ(v 0 , op v0 (R)).
For the induction step, we distinguish two cases. In the first one, assume that m(u, v, v 0 ) = u --equivalently, Π(m, u) = Π(u -, u) = {u -, u}. A shortest (u, v)-path is the concatenation of the shortest (u, u -)-path of length |R| with a shortest (u -, v)-path, and u -∈ I(v 0 , v). The largest distance d(u, v) we can have, as for the base case, is

ψ(u, R) = |R| + φ(u -, op u -(R)).
In the second case, m ̸ = u -, an inductive formula allows us to obtain ψ(u, R). A consequence of Lemma 18 is that, for two consecutive milestones in Π(u, v), say u and u + w.l.o.g, then L u + ,v is L u,v -parallel. This observation, applied to the penultimate milestone, provides us with the following theorem.

Lemma 20 (Inductive formula for labels ψ [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]) Let u, v ∈ V and u ∈ I(v 0 , v). Let L be a POF outgoing from v and w the anti-basis of hypercube (v, L). The following propositions are equivalent:

(i) vertex v is the penultimate milestone of (u, w): π(u, w) = v, (ii) the milestones of (u, w) are the milestones of (u, v) with w:

Π(u, w) = Π(u, v) ∪ {w}, (iii) the POF L is L u,v -parallel.
Set Π(m, u) admits at least three milestones: m, u -, and u. Let R -be the POF incoming to u -which is the ladder set (but also the signature) of (i) the milestone just before u -and (ii) u -. According to Lemma 20, vertex u -is the penultimate milestone of (m, u) if and only if R -∪ {E j } is not a POF, for each E j ∈ R. For this reason, value ψ(u, R) can be expressed as:

ψ(u, R) = max R -POF incoming to u - ∀Ej ∈R,R -∪{Ej } not POF (|R| + ψ(u -, R -)) (5)
Our algorithm consists in taking the maximum value between the two cases. The number of pairs ((u, R), (u -, R -)) which satisfy the condition described in Equation ( 5) is at most 2 2d n: it is identical to the one presented for φ-labelings.

Theorem 8 (Computation of labels ψ [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF]) There is a combinatorial algorithm which determines all labels ψ(u, R) in Õ(2 2d n).

Better time complexity for all eccentricities

The computation of all labels φ(u, L), op u (L) and ψ(u, R) gives an algorithm which determines all eccentricities. Indeed, each eccentricity ecc(u) is a function of certain labels φ and ψ. Let v be a vertex in G such that ecc(u) = d(u, v). If m = m(u, v, v 0 ) = u, then u ∈ I(v 0 , v) and value d(u, v) is given by a label φ(u, L). Otherwise, if m ̸ = u, let u -be the penultimate milestone in Π(m, u) and R be the classes of the hypercube with basis u -and anti-basis u. The eccentricity of u is given by a label ψ(u, R). Conversely, each φ(u, L) and ψ(u, R) is the distance between u and another vertex by definition. Therefore, we have:

ecc(u) = max      max L POF outgoing from u φ(u, L), max R POF incoming to u ψ(u, R)      (6)
In other words, the eccentricity of u is the maximum label φ or ψ centered at u. We can conclude with the main result of this subsection: the eccentricities of any median graph can be determined in linear time multiplied by a simple exponential function 2 O(d) of the dimension d.

Theorem 9 (All eccentricities in Õ(2 2d n)-time for median graphs) There is a combinatorial algorithm computing the list of all eccentricities of a median graph G in time Õ(2 2d n).

Proof We simply determine the labels φ, op and ψ with the algorithms mentioned in Theorem 6, 7, and 8. Thanks to the time improvement obtained for the computation of opposite labels, the overall running time to compute the labels is only Õ(2 2d n). Then, for each vertex u, Equation ( 6) guides us to obtain its eccentricity. We take the maximum over all labels φ(u, L) -they are at most Nu -and all labels ψ(u, R) -they are at most 2 d . As u Nu ≤ 2 d n, the execution time of this operation on all vertices is Õ(2 d n). Therefore, it does not overpass the time complexity needed to determine the labels. □

Tackling the general case

Our new FPT algorithm for computing the list of eccentricities in a median graph has a runtime in 2 O(d) n, with d being the dimension (Theorem 9). This runtime stays subquadratic in n as long as d < α • log n, for some constant α < 1. In what follows, we present a simple partitioning scheme for median graphs into convex subgraphs of dimension at most α • log n, for an arbitrary value of α ≤ 1. By doing so, we obtain (in combination with Theorem 9) the first known subquadratic-time algorithm for computing all eccentricities in a median graph. We start with a simple relation between the eccentricity function of a median graph and the respective eccentricity functions of any two complementary halfspaces.

Lemma 21 Let G be a median graph. For every 1 ≤ i ≤ q, let v ∈ V (H ′ i ) be arbitrary, and let v * be its gate in

∂H ′′ i . Then, ecc(v) = max{ecc H ′ i (v), d(v, v * ) + ecc H ′′ i (v * )}. Proof We have ecc(v) = ecc G (v) = max{d(u, v) | u ∈ V (H ′ i )} ∪ {d(w, v) | w ∈ V (H ′′ i )}. Since H ′ i is convex, we have max{d(u, v) | u ∈ V (H ′ i )} = ecc H ′ i (v).
In the same way, since H ′′ i is gated (and so, convex), we have max{d(w, v)

| w ∈ V (H ′′ i )} = d(v, v * ) + max{d(v * , w) | w ∈ V (H ′′ i )} = d(v, v * ) + ecc H ′′ i (v * ). □
We will use this above Lemma 21 later in our proof in order to compute in linear time the list of eccentricities in a median graph being given the lists of eccentricities in any two complementary halfspaces.

Next, we give simple properties of Θ-classes, to be used in the analysis of our main algorithm in this section (see Lemma 25).

Lemma 22 Let H and G be median graphs. If H is an induced subgraph of G then, every Θ-class of H is contained in a Θ-class of G.
Proof Every square of H is also a square of G. In particular, two edges of H are in relation Θ 0 if and only if, as edges of G, they are also in relation Θ 0 . Since the Θclasses of H (resp., of G) are the transitive closure of its relation Θ 0 , it follows that every Θ-class of H is contained in a Θ-class of G. □

This above Lemma 22 can be strenghtened in the special case of isometric subgraphs, namely:

Lemma 23 Let H and G be median graphs, and let E 1 , E 2 , . . . , Eq denote the Θclasses of G. If H is an isometric subgraph of G then, the Θ-classes of H are exactly the nonempty subsets among

E i ∩ E(H), for 1 ≤ i ≤ q.
Proof It is known [START_REF] Winkler | Isometric embedding in products of complete graphs[END_REF] that two edges uv, xy of G are in the same Θ-class if and only

if d G (u, x) + d G (v, y) ̸ = d G (u, y) + d G (v, x).
In particular, since H is isometric in G, two edges of H are in the same Θ-class of H if and only if they are in the same Θ-class of G. □

An important consequence of Lemma 22 is the following relation between the dimension d of a median graph and the cardinality of its Θ-classes.

Lemma 24 Let G be a median graph, and let

D := max{|E i | | 1 ≤ i ≤ q} be the maximum cardinality of a Θ-class of G. Then, d = dim(G) ≤ ⌊log D⌋ + 1.
Proof Any induced d-dimensional hypercube of G contains exactly 2 d-1 edges of its Θ-classes. □

We are now ready to present our main technical contribution in this section.

Lemma 25 If there is an algorithm for computing all eccentricities in an n-vertex median graph of dimension at most d in Õ(c d • n) time, then in Õ(n 2-1 1+log c ) time we can compute all eccentricities in any n-vertex median graph.

Proof Let G be an n-vertex median graph. We compute its Θ-classes E 1 , E 2 , . . . , Eq, that takes linear time (Lemma 2). For some parameter D (to be fixed later in the proof), let us assume without loss of generality E 1 , E 2 , . . . , Ep to be the subset of all Θ-classes of cardinality ≥ D, for some p ≤ q. Note that we have p ≤ m/D = Õ(n/D), where m is the number of edges in G.

We reduce the problem of computing all eccentricities in G to the same problem on every connected component of G\(E 1 ∪E 2 ∪. . .∪Ep). More formally, we construct a rooted binary tree 1 T , whose leaves are labelled with convex subgraphs of G. Initially, T is reduced to a single node with label equal to G. Then, for i = 1 . . . p, we further refine this tree so that, at the end of any step i, its leaves are labelled with the connected components of G \ (E 1 ∪ E 2 ∪ . . . ∪ E i ). An example of T is shown in Figure 14 with D = 3 and two Θ-classes reaching this cardinality bound.

For that, we proceed as follows. We consider all leaves of T whose label H satisfies E(H) ∩ E i ̸ = ∅. By Lemma 23, E(H) ∩ E i is a Θ-class of H. Both halfspaces of E i become the left and right children of H in T . Recall that the leaves of T at this step i are the connected components of G \ (E 1 ∪ E 2 ∪ . . . ∪ E i-1 ), and in particular that they form a partition of V (G). Therefore, each step takes linear time by reduction to computing the connected components in vertex-disjoint subgraphs of G. Overall, the total time for constructing the tree T is in O(pm) = Õ(n 2 /D).

E 1 E 2 H ′′ 1 H ′ 1
Fig. 14: An example of tree T associated with a graph G for D = 3: here, p = 2.

Then, we compute the list of eccentricities for all the subgraphs labelling a node, by dynamic programming on T . In particular, doing so we compute the list of eccentricities for G because it is the label of the root. There are two cases:

• If H labels a leaf (base case) then, we claim that we have dim(H) ≤ ⌊log D⌋+ 1. Indeed, by Lemma 22, every Θ-class of H is contained in a Θ-class of G. Since we removed all Θ-classes of G with at least D edges, the claim now follows from Lemma 24. In particular, we can compute the list of all eccentricities for

H in Õ(c ⌊log D⌋+1 |V (H)|) = Õ(D log c |V (H)|) time.
Recall that the leaves of T partition V (G), and therefore, the total runtime for computing the list of eccentricities for the leaves is in Õ(D log c n). • From now on, let us assume H labels an internal node of T (inductive case).

Let H ′ i , H ′′ i be its children nodes, obtained from the removal of E(H) ∩ E i for some 1 ≤ i ≤ p. -For convenience, we will say later in the proof that

H is an i-node. -Recall that E(H) ∩ E i is a Θ-class of H. In particular, H ′ i ,
v ∈ V (H ′ i ) its gate v * ∈ ∂H ′′ i and the distance d(v, v * ).
The respective lists of eccentricities for H ′ i and H ′′ i were pre-computed by dynamic programming on T . Furthermore, we can compute the gate v * and d(v, v * ) for every vertex v ∈ V (H ′ i ), in total Õ(|V (H)|) time, by using a modified BFS rooted at H ′′ i (we refer to [START_REF] Chepoi | Distance labeling schemes for cubefree median graphs[END_REF]Lemma 17] for a detailed description of this standard procedure). Overall (by proceeding the same way for H ′′ i as for H ′ i ) we can compute the list of eccentricities for H in Õ(|V (H)|) time. This is in total Õ(n) time for the i-nodes (i.e., because they were leaves of T at step i, and therefore, they are vertex-disjoint), and so, in total Õ(pn) = Õ(n 2 /D) time for all the internal nodes.

The total runtime for our algorithm is in Õ(n 2 /D + D log c n), that is optimized for

D = n 1 log c+1 . □ Theorem 10
There is an Õ(n 5/3 )-time algorithm for computing all eccentricities in any n-vertex median graph.

Proof This result directly follows from the combination of Theorem 9 with Lemma 25 (applied for c = 4). □

Observe that the design of a linear FPT algorithm for eccentricities in Õ(c d n) with c < 4 would imply a lower subquadratic constant for this problem.

Generalization and improvements

In this section, we discuss some consequences and possible improvements of the algorithms established in Section 4.

First, we focus on another metric parameter called reach centrality. We prove that it can be computed if the labelings φ, op, and ψ are already known. A consequence is the existence of an exact algorithm for the reach centrality in Õ(2 3d n) on median graphs.

Second, we propose a discrete structure strongly related to both POFs and hypercubes but slightly different to them: Maximal Outgoing POFs, also called MOPs. We introduce a different way to compute labelings φ, op and ψ based on this structure. This yields a second subquadratic-time algorithm which determines all eccentricities with a better running time.

Reach centrality

In this subsection, we propose a linear FPT algorithm, parameterized by d, dedicated to the computation of all reach centralities of a median graph G. The reach centrality RC(u) of a vertex u is a parameter related to the length of shortest paths on which vertex u lies. The farther a vertex u is from the two extremities of a shortest path traversing it, the larger the reach centrality of u is. This notion originally inspired some efficient routing strategies on road networks [START_REF] Gutman | Reach-based routing: A new approach to shortest path algorithms optimized for road networks[END_REF]. The relationship between reach centrality and the well-known metric parameters has been studied: Abboud et al. [START_REF] Abboud | Subcubic equivalences between graph centrality problems, APSP and diameter[END_REF] proved that determining the diameter and the reach centrality are equivalent under subcubic reductions. The formal definition of RC(u) follows.

RC(u) = max u∈I(s,t) min {d(s, u), d(u, t)} (7)
In Theorem 9, we showed that all eccentricities of a median graph are functions of the labelings φ, op, and ψ. Here, a similar result is established for the reach centralities.

We begin with a first observation which will be useful to state the dependence of RC on the labels already computed. Under a certain orthogonality condition (the R-parallelism of L), for any pair of POFs R and L respectively incoming in and outgoing from u ∈ V , there are two vertices s, t such that d(u, s) = φ(u, L), d(u, t) = ψ(u, R) and u ∈ I(s, t).

Theorem 11 Let u ∈ V , R be a POF incoming into u and L a POF outgoing from u such that L is R-parallel. There exists a pair (s, t) of vertices satisfying the following properties:

• Vertex u belongs to interval I(v 0 , s) and L u,s = L,

• The median m = m(s, t, v 0 ) is different from u and L m,u = R.
• The distance d(u, s) and d(u, t) are given by the labels: d(u, s) = φ(u, L) and d(u, t) = ψ(u, R). • Vertex u belongs to the interval I(s, t).

Proof Let s be a vertex such that u ∈ I(v 0 , s), Lu,s = L and d(u, s) = φ(u, L). Let t be a vertex such that Lm,u = R for m = m(u, t, v 0 ), and d(u, t) = ψ(u, R). By definition of labels φ and ψ, such vertices exist. At this moment, the three first bullets are verified. To show the fourth one, u ∈ I(s, t), we prove that the signatures σu,s and σ u,t are disjoint. Assume there is a Θ-class E i ∈ σu,s ∩ σ u,t .

Claim 1: u ∈ H ′ i . As E i ∈ σu,s, any shortest (u, s)-path contains an edge of E i . Let (u ′ , v ′ ) be one of these edges of E i which is as close as possible from u. Vertex u ′ -the endpoint of this edge closer to u -belongs to ∂H ′ i . Moreover, there is a shortest (u, s)-path Pu,s passing through (u ′ , v ′ ) because v ′ is the gate of u in H ′′ i . As u ∈ I(v 0 , s) and u ′ ∈ I(u, s), then u ∈ I(v 0 , u ′ ). We know that both v 0 and u ′ belong to H ′ i : by convexity of halfspaces, u ∈ H ′ i . Claim 2: u ∈ H ′′ i . We have E i ∈ σ u,t : we prove that E i is necessarily in σm,u and not in σ m,t . The class E i cannot form a POF if we add it to R. We already know it if E i ∈ L. We prove that: if it was the case for a class E i ∈ σu,s\L, then it would imply the orthogonality of R and all Θ-classes of L, a contradiction. Indeed, let z be the vertex such that

E -(z) = R ∪ {E i }. We have v ′ , z ∈ ∂H ′′ i . As v ′ is the gate of u in H ′′
i , there is a shortest (u, z)-path passing through (u ′ , v ′ ). We denote by ∂H ′′ R the intersection of all ∂H ′′ j for all E j ∈ R. As u, z ∈ ∂H ′′ R , which is convex, all vertices metrically between u and z belong to ∂H ′′ R , in particular v ′ . The ladder set of u, v ′ is the same as u, s because v ′ does not belong to the hypercube Q u,L of basis u and signature L: L u,v ′ = L. In brief, Q u,L ⊊ I(u, v ′ ). So, all Θ-classes of R are adjacent to the vertices of Q u,L , a contradiction as R ∪ L is not a POF.

We know now that there is a class E j ∈ R such that E i and E j are parallel. Thus, H ′′ i ⊊ H ′′ j . Suppose, by way of contradiction, that E i ∈ σ m,t . Vertex t is in H ′′ i , so it is also in H ′′ j . As E j ∈ R ⊆ σm,u, then m ∈ H ′ j : m and t are not in the same halfspace of E j . In other words, E j ∈ σ m,t . This is a contradiction because E j is both in σm,u and σ m,t while m is metrically between u and t. Any shortest (u, t)-path should pass through two edges of E j , which is not possible from Lemma 6. Finally, E i ∈ σm,u and u ∈ H ′′ i . Both Claims 1 and 2 yield a contradiction: the signature sets σu,s and σ u,t are disjoint. Therefore, u ∈ I(s, t). □

We present now an algorithm which determines, for any vertex u ∈ V , a label χ(u). The vertices can be considered in any arbitrary order. The objective is to obtain, at the end of the execution, χ(u) = RC(u), for any vertex u.

To start, we fix all χ(u) equal to 0. Let max ← ---be the operator which modifies the left-hand side variable with the maximum between itself and the righthand side one. Formally, for a ∈ N, χ(u) max ← ---a is equivalent to χ(u) ← max {χ(u), a}. Given a vertex u ∈ V , we proceed in three steps.

Step 1: Reach when u is the median of s, t, v 0 . This step amounts to determining the reach centrality of u if we restrict ourselves to pairs s, t such that u = m(s, t, v 0 ). Given a vertex s such that u ∈ I(v 0 , s), the extremity t maximizing d(u, t) such that u = m(s, t, v 0 ) is at distance φ(u, op(L u,s )), according to Lemma 19. If d(u, s) ≤ φ(u, L u,s ) ≤ φ(u, op u (L u,s )), then distance d(u, s) has no influence on RC(u) as another candidate -any vertex at distance φ(u, L u,s ) from u -overpasses it. Moreover, if d(u, s) ≤ φ(u, op u (L u,s )) ≤ φ(u, L u,s ), then d(u, s) also cannot be equal to RC(u) because φ(u, op u (L u,s )) overpasses it and will count, according to Lemma 19 and the fact that φ(u, L u,s ) is greater than it. Eventually, if d(u, s) > φ(u, op u (L u,s )), it does not count as we cannot form a pair (s, t) such that u ∈ I(s, t) and d(s, u) ≤ d(u, t). In summary, the only values that have to be taken into account for the reach centrality when u is a median are the φ-labelings φ(u, L). We modify label χ(u) according to these observations.

For any POF L outgoing from u, if φ(u, L) < φ(u, op u (L)), then modify the label χ(u) max ← ---φ(u, L), otherwise do nothing.

Step 2: Reach when u ̸ = m = m(s, t, v 0 ) but is a milestone of m, s. Let L be the ladder set of u, s; L = L u,s and R the anti-ladder set of m, u; R = L m,u . According to Lemma 20, L is R-parallel. Theorem 11 intervenes: there is a pair of vertices s * , t * such that u ∈ I(s, t), L u,s * = L, L m * ,u = R, d(u, s * ) = φ(u, L) and d(u, t * ) = ψ(u, R), where m * = m(s * , t * , v 0 ). As φ(u, L) ≥ d(u, s) and ψ(u, R) ≥ d(u, t), the reach centrality of u in this step can be written as a function of only φ, ψ-labelings. For example, if a POF L admits an anti-ladder set R such that φ(u, L) < ψ(u, R), then it has to be taken into account for the computation of χ(u).

For any pair L, R of POFs respectively outgoing from and incoming to u such that L is R-parallel: if φ(u, L) < ψ(u, R), we modify the label χ(u) max ← --φ(u, L). Otherwise, we set χ(u) max ← ---ψ(u, R).

Step 3: Reach when u ̸ = m = m(s, t, v 0 ) and is not a milestone of m, s. Let u ′ be the milestone of Π(m, s) and u ′′ its successor in Π(m, s) such that u belongs to the hypercube of basis u ′ , anti-basis u ′′ and, hence, signature L = L u ′ ,u ′′ = σ u ′ ,u ′′ . We distinguish two cases.

-Case 1: u ′ is the median of s, t, v 0 . In this case, the distance d(u, s) is less than φ(u ′ , L) -d(u ′ , u). Moreover, the distance d(u, t) is less than d(u ′ , u) + φ(u ′ , op u ′ (L)). So, the reach centrality can be expressed only as a function of labels φ, ψ, and the distance d(u ′ , u).

For any POF L outgoing from some u ′ ∈ V such that u belongs to the hypercube of basis u ′ and signature L, if φ(u ′ , L) -d(u ′ , u) < d(u ′ , u) + φ(u ′ , op u ′ (L)), then we modify the label χ(u

) max ← ---φ(u ′ , L) -d(u ′ , u). Otherwise, we set χ(u) max ← ---d(u ′ , u) + φ(u ′ , op u ′ (L)).
-Case 2: u ′ is not the median of s, t, v 0 . Let R be the anti-ladder set of m, u ′ . Theorem 11 implies the existence of a pair of vertices s * , t * with the same (anti-)ladder sets L and R than u ′ with s, t and such that d(u ′ , s * ) = φ(u ′ , L) and d(u ′ , t * ) = ψ(u ′ , R). Furthermore, Lemma 17 ensures us that a shortest path between u ′ and s * can be prefixed with the Θ-classes of L in any ordering. As a consequence, there is a shortest (u ′ , s * )-path containing u. As φ(u ′ , L) -d(u ′ , u) ≥ d(u, s) and ψ(u ′ , R) + d(u ′ , u) ≥ d(u, t), the reach centrality of u in this step can be written only as a function of φ, ψ-labelings and distance d(u, u ′ ).

For any pair L, R of POFs respectively outgoing from and incoming to some u ′ ∈ V such that L is R-parallel: enumerate all vertices u belonging to the hypercube of basis u ′ and signature L. For each of them, if φ(u ′ , L)-d(u ′ , u) < ψ(u, R)+d(u ′ , u), we modify the label χ(u) max ← ---φ(u ′ , L)-d(u ′ , u). Otherwise, we set χ(u) max ← ---ψ(u ′ , R) + d(u ′ , u). Pseudocode. Algorithm 2 provides us with the pseudocode of this procedure. The steps corresponding to the updates of χ(u) are mentioned as comments, surrounded by symbol #.

The computation of all labels φ, op, and ψ is a necessary preprocessing of this algorithm. We remind the reader that they can be obtained in Õ(2 2d n).

Steps 1, 2 and 3 cover all possible configurations of triplet u, s, t such that RC(u) = min {d(s, u), d(s, t)}. Indeed, either u is the median of s, t, v 0 (Step 1) or not. If not, it is either a milestone of at least one pair among (m(s, t, v 0 ), s) and (m(s, t, v 0 ), t) (Step 2), or not (Step 3). In each situation, both distances d(s, u) and d(u, t) are upper-bounded in function of some label values. Conversely, these upper bounds correspond to the distance between u and certain vertices s * , t * , such that u ∈ I(s * , t * ). Hence, RC(u) can be expressed as a function of labelings φ, op, and ψ, as described in Algorithm 2.

Theorem 12 There is a combinatorial algorithm computing all reach centralities RC(u) of a median graph in Õ(2 3d n).

Proof The correctness of Algorithm 2 is now clear. We focus on its runtime. The most expensive part corresponds to Step 3, Case 2 (line 14). Indeed, we enumerate all triplets (u, L, R): we know they are at most 2 2d n. For each of them, we list all 1: Input: Median graph G, weight function C : V → N, labels φ, op, ψ. 2: Output: Labels χ(u) for any vertex u ∈ V . 3: Initialize χ(u) ← 0 for any vertex u; 4: for every pair (u, L) where L is a POF outgoing from u do 5:

if φ(u, L) < φ(u, op u (L)) then 6:

χ(u)

MOP structure

In this subsection, we introduce a new discrete structure for median graphs, called Maximal Outgoing POFs (MOPs). Each MOP refers to a unique hypercube but the reverse is false. We present a less trivial way to compute the labels φ, op and ψ based on the enumeration of MOPs. Thanks to this result, we obtain an improvement of Theorem 10 via a win-win approach. When d ≤ a * log n (value a * < 1 will be determined in the proof), we can apply Theorem 9. Otherwise, when d > a * log n, we show that G admits a subquadratic number of MOPs and the labels can be computed more efficiently than in Section 4.1.

Definition and relationship with labelings

Recall that a pair made up of a vertex u and a POF L outgoing from this vertex can be seen as a hypercube (of basis u and signature L, which is unique). The MOPs are defined to highlight certain hypercubes which satisfy a maximality property.

Definition 18 (Maximal Outgoing POFs) Pair (u, L) is a MOP if L is outgoing from u and there is no other L ′ ⊋ L outgoing from u.

On one hand, we can associate with each MOP (u, L) the unique hypercube with basis u and signature L. However, there are some hypercubes such that their pair basis-signature is not a MOP. As a trivial example, consider the square C 4 with Θ-classes E 1 , E 2 . The two edges which are incident to v 0 are hypercubes of dimension 1, (v 0 , {E 1 }) and (v 0 , {E 2 }), but are not MOPs since the POF {E 1 , E 2 } is outgoing from v 0 and maximal.

On the other hand, there is an interesting relationship between MOPs and maximal POFs. We remind the reader that maximal POFs are in bijection with maximal induced hypercubes (Theorem 1). Thus, a maximal POF is a MOP if we consider the pair basis-signature of the maximal hypercube representing it. Conversely, MOPs are not necessarily signed with maximal POFs. Let us consider the same trivial example C 4 : the two edges which are not incident to v 0 are MOPs but do not form a maximal hypercube. In brief, MOPs represent some intermediary discrete structure between hypercubes and maximal hypercubes (or maximal POFs).

The execution time of the algorithms (Theorems 9 and 10) we designed to determine the eccentricities of median graphs depend on our methods to compute all labels φ(u, L) and ψ(u, R), which are both in Õ(2 2d n), as stated in Theorems 6 and 8. Both of them consist in listing all pairs (L, R) of POFs such that L (resp. R) is outgoing from (resp. incoming into) vertex u and R ∪ {E i } is not a POF for any E i ∈ L. We show how the MOPs offer an alternative to this "brute force" enumeration. In fact, we can determine all labels by listing only these pairs (L, R) for which (u, L) is a MOP (instead of being only a hypercube).

Theorem 13 Assume graph G has at most Õ(f (d, n)n) MOPs, f (d, n) = o(2 d ).
There is a combinatorial algorithm computing all labels φ(u, L), op u (L), and ψ

(u, R) in Õ(2 d f (d, n)n).
Proof Let u ∈ V , Nu be the number of hypercubes with basis u. Recall that u∈V Nu ≤ 2 d n. We begin with the definition of a DAG H L u for hypercubes. It is called the ladder Hasse diagram of u. Its vertex set is made up of all pairs (u, L) of hypercubes with basis u, in other words, L is outgoing from u. There is an arc

(u, L ′ ) → (u, L) if L ′ ⊊ L and |L ′ | = |L| -1. All diagrams H L u , u ∈ V , can be con- structed in time Õ(2 d n)
. Indeed, all hypercubes can be enumerated in Õ(2 d n) with a BFS (Lemma 12). Then, it suffices, for each (u, L), to consider the at most d subsets L ′ ⊊ L differing from one element from L and connect (u, L ′ ) to (u, L). In this way, we obtain a directed graph where its connected components are the diagrams H L

u . An example of DAG H L u follows. Thanks to the ladder Hasse diagram, computing a list of the MOPs in Õ(2 d n) is straightforward as they are exactly the leaves of the DAGs H L u .

u From now on, we divide the proof into three steps, each one correspond to the computation of a certain type of labels. We begin with the labels φ(u, L).

E 1 E 2 E 3 E 4 (a) Example of star graph Gu E 1 E 2 E 3 E 4 E 1 E 3 E 1 E 4 E 3 E 4 E 2 E 3 E 2 E 4 E 1 E 3 E 4 E 2 E 3 E 4 (b) DAG H L u representing its hypercubes
Computation of φ-labelings. We present a new procedure to compute the labels φ(u, L). A key distinction with the former method should be mentioned: instead of determining labels φ(u, L) only, we also compute another type of labels, denoted by φ ⊆ (u, L). These maximal ladder labels contain in fact the maximum over all labels φ(u, L ′ ) such that L ′ ⊆ L. In brief, φ ⊆ (u, L) = max

L ′ ⊆L φ(u, L ′ ).
We compute these two label functions recursively. First, we propose a recursive procedure to obtain φ(u, L) based on the enumeration of MOPs. We list all triplets (L, u + , L + ) such that (u + , L + ) is a MOP and L is incoming into u + . We denote by u the basis of the hypercube with anti-basis u + and signature L. The base case is the same as in Section 4.1.1. If (u, L) is such that either no edge is leaving the anti-basis u + or all Θ-classes outgoing from u + are orthogonal to L, then fix φ(u, L) = |L|. We pursue with the inductive step. We denote by L + ⊥ the maximal L-parallel subset of L + , i.e. the set containing exactly the Θ-classes E i of L + for which L ∪ {E i } is not a POF. As L + ⊥ ⊆ L + , set L + ⊥ is a POF. The computation of L + ⊥ implies a logarithmic extra cost of O(d) for each MOP (u + , L + ). We write the MOP-equivalent formula of Equation (4).

φ(u, L) = max (u + ,L + ) MOP, L incoming into u ∀Ej ∈L + ⊥ , L∪{Ej } not POF (|L| + φ ⊆ (u + , L + ⊥ )). (8)
We explain why Equation ( 8) is correct. According to Equation (4), φ(u, L) is |L| plus the maximum over all φ(u + , L + * ) -not necessarily MOPs -such that L + * is L-parallel. Assume (u + , L + * ) is not a MOP: there is a MOP (u + , L + ), where

L + * ⊊ L + . As L + ⊥ is the maximal L-parallel subset of L + , we have L + * ⊆ L + ⊥ . So, φ(u + , L + * ) ≤ φ ⊆ (u + , L + ⊥ ) by definition. Conversely, value φ ⊆ (u + , L + ⊥ )
counts in the computation of φ(u, L) because all subsets of L + ⊥ are L-parallel. Therefore, it suffices to consider the MOPs (u + , L + ) with their maximal subset L + ⊥ instead of all hypercubes (u + , L + * ). Second, we explain how the labels φ ⊆ are deduced from the values φ(u, L). Assume that for a given vertex u, all φ(u, L), L outgoing from u, have been determined recursively, thanks to the base case or Equation [START_REF] Bandelt | Mitochondrial portraits of human populations using median networks[END_REF]. We deduce all φ ⊆ (u, L) with the ladder Hasse diagram structure H L u . We proceed inductively. The base case have the same basis and R ⊆ R ′ . On one hand, if (u -, R) is not a MOP, there is a MOP

(u -, R * ), where R ⊊ R * . Let R -be a POF incoming into u -such that R is R --parallel. Let R * ⊥ be the maximal R --parallel subset of R * . Set R * ⊥ is a POF and R ⊆ R * ⊥ by definition. Assume ψ(u, R) = |R| + ψ(u -, R -): this value is counted in ψ ⊇ (u * ⊥ , R * ⊥ ) but not in ψ ⊇ (u, R) if R ̸ = R * ⊥ .
On the other hand, if some R ′ ⊇ R is R --parallel, then R also does. So, we have:

ψ(u, R) = max      |R| + φ(u -, op u -(R)), max (u ′ ,R ′ ) same basis as (u,R) R⊆R ′ ψ ⊇ (u ′ , R ′ )      . ( 10
) Given a basis u -, we compute all nonnegative values ψ ⊇ (u, R) such that u -is the basis of the hypercube with anti-basis u and signature R. To do so, we enumerate all triplets (R -, u -, R) such that R -is incoming into u -and (u -, R) is a MOP. We compute the maximal R --parallel subset R ⊥ of R and apply Equation ( 9). As for φ-labelings, it consist in an enumeration scheme in Õ( 2

d f (d, n)n).
Then, we deduce labels ψ(u, R) of the hypercubes with basis u -. We use the antiladder Hasse diagram H AL u . If (u -, R) is a MOP, then (u, R) is a root of H AL u , and we fix ψ(u, R) as the maximum between its initial value (case m(u, v, v 0 ) = u -) and ψ ⊇ (u, R): it corresponds to Equation (10) when R is maximal. Otherwise, ψ(u, R) can be computed from Equation [START_REF] Cabello | Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs[END_REF]

in function of ψ ⊇ (u ′ , R ′ ) where (u ′ , R ′ ) is a parent of (u, R) in H AL u .
The time cost of this step is at most Õ(2 d n), due to the size of DAG H AL u . In summary, we obtain the same global running time than for labels φ(u, L), which is Õ( 2

d f (d, n)n). □

Cardinality of MOPs

Our objective is now to express the cardinality of MOPs in function of n and d in order to apply Theorem 13 and improve the subquadratic execution time established in Theorem 10. To do so, we establish a relationship between MOPs and the subsets of maximal POFs.

Definition 19 Let p be the application which, given a vertex u and a POF L outgoing from u, returns a pair (L, L * ), where L * is the POF of Θ-classes incoming into the anti-basis of (u, L).

If we restrict application p to MOPs, it returns a pair made up of a maximal POF and one of its subsets.

Lemma 26 (MOPs as subsets of maximal POFs) Let (u, L) be a MOP and p(u, L) = (L, L * ). Then, L * is a maximal POF.

Proof Let u + be the anti-basis of (u, L). Assume, by way of contradiction, that L * is not maximal. There is a

Θ-class E h such that L * * = L * ∪ {E h } is a POF. Let u ′ be the vertex such that E -(u ′ ) = L * * .
For every E i ∈ L * , vertices u + and u ′ belongs to ∂H ′′ i . The intersection of these boundaries, that we denote by ∂H * , is convex. Therefore, all vertices metrically between u + and u ′ belong to ∂H * . For this reason, there is necessarily an edge e incident to u + whose second endpoint is also in ∂H * . Let e = (u + , w) be this edge and we denote by E j its Θ-class. If e is incoming into u + with the v 0 -orientation, then we have a contradiction, since p(u, L) = (L, L * ) ̸ = (L, L * * ). We know that e is outgoing from u + . Recall that E j is orthogonal to any Θ-class of L * . By successive applications of Lemma 8, we show that for any vertex of the hypercube of anti-basis u + and signature L * , among them u, there is an edge of E j outgoing from it. Here comes the contradiction: L is not a maximal POF outgoing from u as L ∪ E j is a POF (L ⊆ L * ). □

Maximal POFs can be interpreted in the crossing graph G # (Definition 6). As it describes the orthogonality of Θ-classes, a POF of G is exactly a clique of G # . Naturally, a maximal POF corresponds to a maximal clique of G # . We provide an upper bound of the number of MOPs of G which depends on the maximal cliques of its crossing graph. Proof We begin with the proof that application p is injective. Let us consider a pair (L, L * ) = p(u, L). There is a unique vertex u + such that E -= L * . Necessarily, if (u, L) = p -1 (L, L * ), then vertex u is the basis of the hypercube with signature L and anti-basis u + , which is unique. Now, application p is restricted to MOPs only. We know it is injective and that, for any MOP (u, L), set L * of p(u, L) = (L, L * ) is a maximal POF. Concretely, the number of MOPs is at most the following value: for each maximal POF, add the number of its nonempty subsets (which is 2 to the power its cardinality minus 1).

We remind the reader that a POF of G corresponds to an induced clique of its crossing graph G # . Naturally, a maximal clique of G # represents a maximal POF. It follows that the number of MOPs of G is at most

C∈C # max (2 |C|-1) ≤ C∈C # max 2 |C| . □
We define a parameter, the maximal clique ratio. Its role is to provide an upper bound of the ratio between the number of MOPs of a median graph and the number of vertices n. We begin with the proof that the complete multipartite graphs maximize the ratio r(H). Next, we show that the more the complete multipartite graph is balanced, the larger r(H) is.

The complete multipartite graphs are exactly the graphs fulfilling the following property: for any non-adjacent vertices u, v, N (u) = N (v). Let Trp(H) be the number of triplets (u, v, w) of vertices of H such that uv / ∈ E, uw / ∈ E, but vw ∈ E. An equivalent way to characterize complete multipartite graphs is Trp(H) = 0. In other words, any graph which is not complete multipartite satisfy Trp(H) > 0.

Theorem 14 Let H be a graph with |V (H)| = q, clique number at most d, which maximizes r(H). If H is not complete multipartite, there is another graph H ′ with |V (H ′ )| = q, clique number at most d, such that r(H ′ ) = r(H) and Trp(H ′ ) < Trp(H).

Proof If H is not complete multipartite, there is a pair u, v of vertices such that (u, v) / ∈ E and N (u) ̸ = N (v). Let Nu (resp. Nv) be the number of cliques of H containing u (resp. v). For x ∈ {u, v}, we denote by Rx the following value: Rx = C∈C max (H) x∈C 2 |C| . For the remainder, we fix ∆R = Rv -Ru and ∆N = Nv -Nu. We define two graphs Hu→v and Hv→u, and compare their maximal clique ratio with the initial graph H.

Graph Hu→v is obtained from H by removing u and adding a copy v ′ of v such that N (v ′ ) = N (v). We have r(Hu→v) =

R[H]+∆R N [H]+∆N ≤ R[H] N [H] , then R[H]-∆R N [H]-∆N ≥ R[H]
N [H] and vice-versa. If the inequality is strict, then we have a contradiction since H is supposed to maximize r(H) for graphs with q vertices and clique number at most d. The only possibility we have is r(H) = r(Hu→v) = r(Hv→u).

We prove that either Hu→v or Hv→u has less triplets with only two adjacent vertices than H. Let Trp u (resp. Trp v ) be the number of triplets of H containing u and not v (resp. v and not u). Let Trp u/v (resp. Trp v/u ) the number of triplets of H containing both u and v, where u is the isolated vertex (resp. v is the isolated vertex). We have By successive applications of this result, for any graph H of clique number at most d maximizing r(H), there exists a complete multipartite graph H ′ with the same ratio and clique number at most d. Turán graphs T (q, d) are the most balanced complete multipartite graphs with q vertices and clique number d. The sizes of two of its independent sets differ by at most one. Now, the objective is to prove that, among complete multipartite graphs, Turán graphs maximize the maximal clique ratio.

Theorem 15 Turán graphs T (q, d) maximize the maximal clique ratio for graphs with q vertices and clique number d.

Proof We consider a complete multipartite graph H with q vertices and clique number d. The vertex set of H can be partitioned into d independent sets A i :

V (H) = d 1 A i . Let α i = |A i |.
Assume, w.l.o.g, that the sizes of sets A i are increasing, i.e. α 1 ≤ α 2 ≤ • • • ≤ α d . Recall that d 1 α i = q. Turán graphs are the graphs such that α d -α 1 ≤ 1.

Assume that, on graph H, α d -α 1 ≥ 2. We prove adding a vertex to A 1 and removing another one from A d increases the maximal clique ratio, without changing q or d. Let H ′ denote the graph after this transformation. All maximal cliques in H have size d, so R [H] = 2 d d 1 α i . The number N [H] of (not necessarily maximal) cliques of H is expressed as: N [H] = J ⊆{1,...,d} j∈J α j . Values R H ′ and N H ′ can be deduced by replacing respectively α 1 and α d by α 1 + 1 and α d -1. We assess the quotient between r(H ′ ) and r(H). Certain details of our calculations are omitted to keep the paper readable, we restrict ourselves to the main steps of the reasoning.

r(H ′ ) r(H) = R[H ′ ] R[H] N [H ′ ] N [H] = α1+1 α1 α d -1 α d 1 + α d -α1-1 (α1+1)(α d +1) = 1 + 1 α 1 (α 1 + 2) 1 - 1 α 2 d > 1.
Indeed, as α d -α 1 ≥ 2, one can check that 1 +

r(G # ) ≤ 2 d ( q d ) d d j=1 d j ( q d ) j ≤ 2 d ( q d ) d (1 + q d ) d (11)
The number of cliques of G # is exactly the number of POFs of G. Therefore, n = |V (G)| = (1+ q d ) d . We fix a = d log n , we have 0 < a ≤ 1. We obtain that 2 d a = (1+ q d ) d and, thus, q d = 2

1 a -1. Finally, we inject this equality into Equation [START_REF] Ducoffe | Diameter, eccentricities and distance oracle computations on H -minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension[END_REF]. □

By observing the expression of function f (d, n), we see that the larger the dimension d, the smaller the number of MOPs. The following result comes from the win-win approach we announced earlier. When the dimension d is lower than a certain threshold (below 1 2 , the details are in the proof), we can apply the linear FPT algorithm of Theorem 9 which gives a subquadratic running time. Otherwise, when d is larger than this threshold, the number of MOPs admits an upper bound less than 2 2d n and can be enumerated to obtain all eccentricities via the labelings (Theorem 13).

Theorem 16 There is a combinatorial algorithm determining all eccentricities in Õ(n 1.6456 ).

Proof Let a = d log n and we define two functions: f (x) = 22 One one hand, according to Theorem 9, there is a combinatorial algorithm determining all eccentricities in Õ(2 2d n) = Õ(n 1+2a ).

On the other hand, according to Theorem 13 and Corollary 4, we can compute all labels φ, op and ψ in time Õ(2 d (f (a)) d n). Using the reduction scheme of Theorem 25, we can compute all eccentricities in time Õ(n g(a) ).

To obtain the best runtime possible, we have to minimize the subquadratic constant h(a) = max {1 + 2a, g(a)}. Function h admits a unique minimum for 0 < a ≤ 1, which is reached for a certain a * we can approximate by 0.3327 ≤ a * ≤ 0.3328. This gives h(a * ) ≃ 1.6456.

We describe the combinatorial algorithm computing all eccentricities in Õ(n h(a * ) ). List all hypercubes as stated in Lemma 12. If d log n ≤ a * , then apply the linear FPT algorithm evoked in Theorem 9. Otherwise, if d log n > a * , then compute the labelings by enumerating the MOPs of G (Theorem 13). Deduce from it all eccentricities. Eventually, apply the reduction scheme proposed in Lemma 25. □

Conclusion

As a natural extension of this work, the question of designing a linear-time or quasilinear-time algorithm to compute the diameter and all eccentricities of median graphs is now open. With the recursive splitting procedure of Lemma 25, unfortunately, the best execution time we could obtain at best is Õ(n would "suffice" to propose a FPT combinatorial algorithm which computes all labels in Õ(2 d n) in order to obtain such time complexity. We see the MOP-approach as a gateway to identify such a procedure. Another -certainly easier -objective after this work is to adapt the recursive splitting of Lemma 25 for reach centralities. We tried to define a weighted version of the reach centralities problem in order to fit them to the halfspace separation, but this task seems to be not so easy. Our hope is to obtain a subquadratic-time algorithm computing reach centralities in median graphs.

Eventually, we note two lines of research on which this paper could have some influence: (i) the study of efficient algorithms for the computation of other metric parameters on median graphs (perhaps, the betweeness centrality [START_REF] Abboud | Subcubic equivalences between graph centrality problems, APSP and diameter[END_REF]) and (ii) the design of subquadratic-time algorithms for the diameter and all eccentricities on larger families of graphs (almost-median or semimedian graphs [START_REF] Bresar | Characterizing almost-median graphs[END_REF][START_REF] Klavzar | Characterizing almost-median graphs II[END_REF] for example). Concerning the betweeness centrality, our intuition is that the labeling framework introduced [START_REF] Bergé | Diameter, radius and all eccentricities in linear time for constant-dimension median graphs[END_REF] does not suffice to describe the number of (u, v)-paths passing through some vertex, which is exactly what betweeness centrality assesses.

4 Fig. 1 :

 41 Fig. 1: Examples of median graphs

Fig. 4 :

 4 Fig. 4: Properties of POFs

Lemma 11 (

 11 Number of hypercubes) α(G) ≤ 2 d n.

Fig. 5 :

 5 Fig. 5: A cycle C 5 and its simplex graph K(C 5 )

  a), where R + (a) contains indices with boolean true, while R -(a) contains indices with boolean false. In this example, R + (a) = {E i2 } and R -(a) = {E i1 }. Set R + (a) is a POF: it contains Θ-classes which are pairwise orthogonal, otherwise R + (a) would not be the subset of a POF belonging to L.

T

  Some nodes of T obtained with the partition refinement over L 0 Some blocks of T : all blocks of layer 0 and 1, one block of layer 2. Node a has layer 2.

Corollary 2

 2 Computing order τω and then OIPR applied with W = E, S = L and τ = τω can be done in O(n(d + log n)).

Fig. 9 :

 9 Fig. 9: Some vertices of the DAG H

Fig. 12 :

 12 Fig. 12: Example of star graph G u

2 :

 2 for every vertex u * belonging to the hypercube of basis u and signature L do 9:χ(u * ) max ← ---min {φ(u, L) -d(u, u * ), φ(u, op u (L)) + d(u, u * )}; # Step 3-1 # 10: endfor 11: for every POF R incoming into u such that L is R-parallel do 12: χ(u) max ← ---min {φ(u, L), ψ(u, R)} # Step 2 # ; 13:for every vertex u * belonging to the hypercube of basis u and signature L do 14:χ(u * ) max ← ---min {φ(u, L) -d(u, u * ), ψ(u, R) + d(u, u * )}; # Step 3Computation of labels χvertices lying on the hypercube of basis u and signature L, which contains potentially 2 d vertices. The total number of 4-uplets (u, L, R, u * ) considered in line 14 of Algorithm 2 is thus at most 2 3d n. □

Fig. 15 :

 15 Fig. 15: Ladder Hasse diagram H L u

Corollary 3 (

 3 MOPs as subsets of maximal cliques in G # ) Let G # be the crossing graph of G and C # max be the set of maximal cliques of G # . The number of MOPs in G is at most C∈C # max 2 |C| .

Definition 20 (

 20 Maximal clique ratio) The maximal clique ratio r(H) of a graph H is the quotient between the sum of the number of subsets of each maximal clique of H by the number of cliques of H. Formally,r(H) = R [H] N [H] = C∈C max (H) 2 C |C(H)| Observe that, for H = G # , N [H] = |V (G)| = n.The clique number of a graph is the size of its maximum clique. The dimension d of G is also the clique number of G # . Complete multipartite graphs (with clique number d) are the graphs whose vertex set can be partitioned into independent sets A i , 1 ≤ i ≤ d, and any pair of vertices belonging to a different set form an edge.

  R[H]+∆RN [H]+∆N , as u and v cannot belong to the same clique. Conversely, graph Hv→u is obtained from H by removing v and adding a copy u ′ of u such that N (u ′ ) = N (u). We have r(Hv→u) =R[H]-∆R N [H]-∆N .Both Hu→v and Hv→u do not increase the clique number of H. One can check that if

  Trp(Hu→v) = Trp(H) + Trpv -Trp u -Trp u/v -Trp v/u , Trp(Hv→u) = Trp(H) + Trp u -Trp v -Trp u/v -Trp v/u .At least one of these values is smaller than Trp(H), otherwise Trp u/v = Trp v/u = 0, which is equivalent to saying N (u) = N (v), a contradiction. □

1 (

 1 α1+2) 2 is greater than 1 for any value of α 1 .□Naturally, we use the maximal clique ratio of Turán graphs to deduce an upper bound for the number of MOPs of any median graph G.

Corollary 4 Proof

 4 The number of MOPs in a median graph is O(f (d, n)n), where f (d, n) According to Corollary 3, the number of MOPs of a median graph G is upperbounded by r(G # )n. Furthermore, Theorem 15 states that the balanced complete multipartite graphs maximize r(H). Hence,

  Lemma 17 ([26]) Every ladder set Lu,v is a POF. For any ordering τ of the Θclasses in Lu,v, there is a shortest (u, v)-path such that, for any 1 ≤ i ≤ |Lu,v|, the i th first edge of the path belongs to the i th Θ-class of Lu,v in ordering τ .

  H ′′ i are gated subgraphs. By Lemma 21, we can compute in O(|V (H ′ i )|) time the eccentricities in H of all vertices in H ′ i if we are given as input: the list of eccentricities in H ′ i , the list of eccentricities in H ′′ i , and for every

Subquadratic-time algorithm for the diameter on median graphs

Subquadratic-time algorithm for the diameter on median graphs

This tree T is independent to the one built in Section 3.2

). Reaching this bound could represent a first reasonable objective: it

Acknowledgments. This work was supported by a grant of the Romanian Ministry of Research, Innovation and Digitalization, CCCDI -UEFISCDI, project number PN-III-P2-2.1-PED-2021-2142, within PNCDI III

concerns singleton POFs: φ(u, {E i }) = φ ⊆ (u, {E i }). Then, we describe the induction step. We modify the value φ ⊆ (u, L) by comparing φ(u, L) with all φ ⊆ (u, L ′ ), where L ′ ⊊ L, |L ′ | = |L|-1. In other words, we initialize φ ⊆ (u, L) as φ(u, L) and, for each arc (u,

we transfer the φ ⊆ -labelings from the roots to the leaves of the diagram H L u . To compute labels φ(u, L), the enumeration of MOPs is needed to apply Equation [START_REF] Bandelt | Mitochondrial portraits of human populations using median networks[END_REF]. For each MOP (u + , L + ), we have to consider all POFs L incoming into u, which gives a total of at most Õ(2 d f (d, n)n) triplets (L, u + , L + ), as the number of MOPs is Õ(f (d, n)n). The logarithmic extra costs do not increase this runtime. To compute labels φ ⊆ (u, L), our induction is based on the structure of all diagrams H L u . The total size (number of arcs) of the DAG H L u is Õ(Nu) as each element has at most d parents. Therefore, the execution time needed to determine all φ ⊆ (u, L) does not exceed Õ(2 d n). In summary, the entire procedure to compute φ, φ

Computation of op-labelings. We already know that all labels op u (L) can be determined in time Õ(2 d n), according to Theorem 7.

Computation of ψ-labelings. Our inductive procedure to determine all labels ψ(u, R) based on the MOP structure is in fact very close to the one produced for φ-labelings.

We define the anti-ladder Hasse diagram H AL u of u. Its vertex set is made up of all pairs (u, R) of hypercubes with anti-basis u and a POF R incoming into u.

There is an arc (u ′ , R ′ ) → (u, R) if both hypercubes (defined by their anti-basis and signature) have the same basis, R ′ ⊋ R and |R ′ | = |R| + 1. As for diagrams H L u , all DAGs H AL u can be constructed in time Õ(2 d n) with a standard BFS. As for φ-labelings, we define two label functions which will be computed jointly. However, the description is a bit trickier. We compute not only labels ψ(u, R) but also the new ones ψ ⊇ (u, R). Contrary to φ ⊆ -labelings, value ψ ⊇ (u, R) is not so easy to define. To understand, we recall the inductive process to compute labels ψ(u, R) in Section 4.1.3.

Remember that there are two cases. Let u -be the basis of (u, R). First, value ψ(u, R) can be given by a distance d(u, v) such that m(u, v, v 0 ) = u -. In this case, ψ(u, R) = |R| + φ(u -, op u -(R)). In the new procedure, we initialize all ψ(u, R) with this value. Second, we may have m(u, v, v 0 ) ̸ = u -. In this case, value ψ(u, R) is given by the recursive formula in Equation [START_REF] Barthélemy | Median graphs, parallelism and posets[END_REF]. We can now define labels ψ ⊇ . Let R -be a POF incoming into u -and assume that (u -, R) is a MOP. Let R ⊥ be the set containing exactly the Θ-classes E i of R such that R is R --parallel. We denote by u ⊥ the anti-basis of the hypercube with basis u -and signature R ⊥ . Then, value |R| + ψ(u -, R -), which counts originally in the computation of ψ(u, R) (Equation ( 5)), will count only for the computation of ψ ⊇ (u ⊥ , R ⊥ ). More formally,

Observe that certain pairs (u, R) may not admit a value ψ ⊇ (u, R) according to this definition. In this case, we simply fix ψ ⊇ (u, R) = 0. Now, we show that value ψ(u, R), in the case m ̸ = u -, is exactly the maximum over all ψ ⊇ (u ′ , R ′ ) such that both hypercubes (defined by anti-basis and signature)