# Subquadratic-time algorithm for the diameter and all eccentricities on
median graphs

Pierre Bergé  LIMOS, CNRS, Université Clermont Auvergne, France,
<EMAIL_ADDRESS>IRIF, CNRS, Université de Paris, France  Guillaume Ducoffe
National Institute for Research and Development in Informatics, Romania
University of Bucharest, Romania  Michel Habib  IRIF, CNRS, Université de
Paris, France

###### Abstract

On sparse graphs, Roditty and Williams [2013] proved that no
$O(n^{2-\varepsilon})$-time algorithm achieves an approximation factor smaller
than $\frac{3}{2}$ for the diameter problem unless SETH fails. In this
article, we solve an open question formulated in the literature: can we use
the structural properties of median graphs to break this global quadratic
barrier?

We propose the first combinatiorial algorithm computing exactly all
eccentricities of a median graph in truly subquadratic time. Median graphs
constitute the family of graphs which is the most studied in metric graph
theory because their structure represents many other discrete and geometric
concepts, such as CAT(0) cube complexes. Our result generalizes a recent one,
stating that there is a linear-time algorithm for all eccentricities in median
graphs with bounded dimension $d$, i.e. the dimension of the largest induced
hypercube. This prerequisite on $d$ is not necessarily anymore to determine
all eccentricities in subquadratic time. The execution time of our algorithm
is $O(n^{1.6408}\log^{O(1)}n)$.

We provide also some satellite outcomes related to this general result. In
particular, restricted to simplex graphs, this algorithm enumerates all
eccentricities with a quasilinear running time. Moreover, an algorithm is
proposed to compute exactly all reach centralities in time
$O(2^{3d}n\log^{O(1)}n)$.

##  1 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 [4, 16], CAT(0) cube complexes [6, 20], abstract models of
concurrency [12, 41], and genetics [9, 11]. Let $d(a,b)$ be the length (i.e.
number of edges) of the shortest $(a,b)$-path for $a,b\in 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\in V$, the intersection $I(x,y)\cap I(y,z)\cap
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\in 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
$\mbox{{ecc}}(v)$ of a vertex $v$ is the maximum length of a shortest path
starting from $v$: $\mbox{{ecc}}(v)=\max_{w\in V}d(v,w)$. The diameter is thus
the maximum eccentricity.

###  1.1 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\left|E\right|)$, with
$n=\left|V\right|$. As median graphs are relatively sparse,
$\left|E\right|\leq 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
[2, 18, 24]. Many works have also been devoted to approximation algorithms for
this parameter. Chechik et al. [19] showed that the diameter can be
approximated within a factor $\frac{3}{2}$ in time
$\tilde{O}(m^{\frac{3}{2}})$ on general graphs. On sparse graphs, it was shown
in [40] that no $O(n^{2-\varepsilon})$-time algorithm can achieve an
approximation factor smaller than $\frac{3}{2}$ for the diameter unless the
Strong Exponential Time Hypothesis (SETH) fails.

Median graphs are bipartite and can be isometrically embedded into hypercubes.
They are the 1-skeletons of CAT(0) cube complexes [20] and the domains of
event structures [12]. They admit structural properties, such as the Mulder’s
convex expansion [37, 38]. They are strongly related to hypercubes retracts
[5], Cartesian products and gated amalgams [6], but also Helly hypergraphs
[36]. They do not contain induced $K_{2,3}$, otherwise a triplet of vertices
would admit at least two medians. The dimension $d$ of a median graph $G$ is
the dimension of its largest induced hypercube. The value of this parameter is
at most $\lfloor\log n\rfloor$ and meets this upper bound when $G$ is an
hypercube. Moreover, parameter $d$ takes part in the sparsity of median
graphs: $\left|E\right|\leq dn$.

An important concept related to median graphs is the equivalence relation
$\Theta$. This is the reflexive and transitive closure of relation
$\Theta_{0}$, where two edges are in $\Theta_{0}$ if they are opposite in a
common 4-cycle. A $\Theta$-class is an equivalence class of $\Theta$. Each
$\Theta$-class of a median graph forms a matching cutset, splitting the graph
into two convex connected components, called halfspaces. The number $q\leq n$
of $\Theta$-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\leq 2$ [32]. A recent LexBFS-based algorithm [14] identifies
the $\Theta$-classes in linear time $O(\left|E\right|)=O(dn)$.

Two subquadratic-time algorithms have been proposed for the recognition of
median graphs. Using convex characterizations of halfspaces, Hagauer et al.
[28] showed that median graphs can be recognized in
$O(n^{\frac{3}{2}}\sqrt{n})$. In [30], a bijection between median and
triangle-free graphs make the recognition algorithms for triangle-free graphs
work on median ones [3]. 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(\left|E\right|)$ [14]. Subfamilies of median graphs have also been studied.
There is an algorithm computing the diameter and the radius in linear time for
squaregraphs [21]. 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 [23], using distance and routing labeling schemes proposed in
[22]. Eventually, a linear-time algorithm [15] for the diameter on constant-
dimension median graphs was proposed, i.e. for median graphs satisfying
$d=O(1)$.

The existence of a truly subquadratic-time algorithm for the diameter on all
median graphs is open and was recently formulated in [14, 23]. 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 linear-time
algorithm was recently designed). In this article, we propose the first
subquadratic-time algorithm computing all eccentricities on median graphs.

###  1.2 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\cup\left\\{v\right\\}$. These edges form
the set $E_{K}$. All simplex graphs are median [6, 13]. Moreover, we observe
that simplex graphs admit an interesting property: they admit a central vertex
- representing the empty clique - and every $\Theta$-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 the size of
certain sets of pairwise orthogonal $\Theta$-classes (POFs). Based on that
property, we order the POFs in function of their size 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 [15] 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 $\tilde{O}(2^{2d}n)$, where notation $\tilde{O}$ 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 $\tilde{O}(2^{2d}n)$: Theorem 10, 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 $\Theta$-class. With our
construction, the leaves of this recursive tree are median graphs with
dimension at most $\frac{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 $\tilde{O}(n^{\frac{5}{3}})$: Theorem 11, Section 4.2.

These three results so far stand as the core of our article (first line of
Table 1). They put in evidence fast algorithms for the computation of
eccentricities on median graphs. In particular, the last one solves a
challenging open question: the existence of subquadratic-time exact algorithms
for this problem.

| Function of $d,n$ | Function of $n$
---|---|---
Main results | $\tilde{O}(4^{d}n)$ | $n^{\frac{5}{3}}$
Improvements | $\tilde{O}(3.5394^{d}n)$ | $n^{1.6408}$
Table 1: Best running times obtained for the computation of eccentricities on
median graphs

We terminate the article (Section 5) with some improvements of the framework
we designed. We focus first on the computation of all reach centralities [26]
in a median graph. The reach centrality of a vertex $u$ is the maximum value
$\min\left\\{d(s,u),d(u,t)\right\\}$ over all pairs $s,t$ satisfying $u\in
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 $\tilde{O}(2^{3d}n)$: Theorem 13, Section 5.1.

Then, we define a new discrete structure on median graphs: the maximal
outgoing POFs (MOPs), generalizing the POFs used throughout the paper and
defined in [15]. 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 of median
graphs in $\tilde{O}(n^{\beta})$, where $\beta=1.6456$: Theorem 17, Section
5.2.

Eventually, we present a new relationship between POFs which allows us to
improve the running time of the linear-time FPT algorithm.

  * •

There is a combinatorial algorithm determining all eccentricities of median
graphs in $\tilde{O}(3.5394^{d}n)$: Corollary 5, Section 5.3.

Combining this new tool with the techniques associated with MOPs, we obtain a
third subquadratic-time algorithm in this paper for the computation of
eccentricities on median graphs.

  * •

There is a combinatorial algorithm determining all eccentricities of median
graphs in $\tilde{O}(n^{\gamma})$, where $\gamma=1.6408$: Theorem 21, Section
5.3.

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.

Table 1 summarizes the results of our paper. We would like to distinguish the
contributions of Sections 3 and 4, which represent significant advances for
the computation of metric parameters on median graphs, with the contributions
of Section 5 which consist in improvements of the latter.

###  1.3 Organization

In Section 2, we remind the definition of median graphs. The well-known
properties and concepts related to them are listed, among them
$\Theta$-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. We also introduce a new relationship between POFs. Eventually, we
conclude in Section 6 and give some directions of research which could follow
the contributions of this article.

##  2 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
$\Theta$-classes, which are equivalences classes over the edge set, and the
Pairwise Orthogonal Families (POFs) characterizing $\Theta$-classes belonging
to a common hypercube.

###  2.1 $\Theta$-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\in V$, i.e. the set of vertices adjacent to $u$ in $G$. We extend it
naturally: for any set $A\subseteq V$, the neighborhood $N(A)$ of $A$ is the
set of vertices outside $A$ adjacent to some $u\in A$.

Given two vertices $u,v\in V$, let $d(u,v)$ be the distance between $u$ and
$v$, i.e. the length of the shortest $(u,v)$-path. The eccentricity
$\mbox{{ecc}}(u)$ of a vertex $u\in V$ is the length of the longest shortest
path starting from $u$. Put formally, $\mbox{{ecc}}(u)$ is the maximum value
$d(u,v)$ for all $v\in V$: $\mbox{{ecc}}(u)=\max_{v\in V}d(u,v)$. The diameter
of graph $G$ is the maximum distance between two of its vertices:
$\mbox{{diam}}(G)=\max_{u\in V}\mbox{{ecc}}(u)$.

We denote by $I(u,v)$ the interval of pair $u,v$. It contains exactly the
vertices which are metrically between $u$ and $v$: $I(u,v)=\left\\{x\in
V:d(u,x)+d(x,v)=d(u,v)\right\\}$. The vertices of $I(u,v)$ are lying on at
least one shortest $(u,v)$-path.

We say that a set $H\subseteq V$ (or the induced subgraph $G\left[H\right]$)
is convex if $I(u,v)\subseteq H$ for any pair $u,v\in H$. Moreover, we say
that $H$ is gated if any vertex $v\notin H$ admits a gate $g_{H}(v)\in H$,
i.e. a vertex that belongs to all intervals $I(v,x)$, $x\in H$. For any $x\in
H$, we have $d(v,g_{H}(v))+d(g_{H}(v),x)=d(v,x)$. Gated sets are convex by
definition.

Given an integer $k\geq 1$, the hypercube of dimension $k$, $Q_{k}$, is a
graph representing all the subsets of $\left\\{1,\ldots,k\right\\}$ as the
vertex set. An edge connects two subsets if one is included into the other and
they differ by only one element. Hypercube $Q_{2}$ is a square and $Q_{3}$ is
a $3$-cube.

######  Definition 1 (Median graph).

A graph is median if, for any triplet $x,y,z$ of distinct vertices, the set
$I(x,y)\cap I(y,z)\cap I(z,x)$ contains exactly one vertex $m(x,y,z)$ called
the median of $x,y,z$.

Observe that certain well-known families of graphs are median: trees, grids,
squaregraphs [8], and hypercubes $Q_{k}$. Median graphs are bipartite and do
not contain an induced $K_{2,3}$ [6, 29, 37]. They can be obtained by Mulder’s
convex expansion [37, 38] starting from a single vertex.

(a) Tree, $d=1$

(b) Squaregraph, $d=2$

(c) 4-cube, $d=4$

Figure 1: Examples of median graphs

Now, we define a parameter which has a strong influence on the study of median
graphs. The dimension $d=\mbox{dim}(G)$ of a median graph $G$ is the dimension
of the largest hypercube contained in $G$ as an induced subgraph. 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\leq 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 [8], 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 $\Theta$-classes which is a key ingredient of several
existing algorithms [14, 28, 30].

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

######  Lemma 1 (Convex$\Leftrightarrow$Gated [6, 14]).

Any convex subgraph of a median graph is gated.

To improve readibility, edges $(u,v)\in E$ are sometimes denoted by $uv$. We
remind the notion of $\Theta$-class, which is well explained in [14], and
enumerate some properties related to it. We say that the edges $uv$ and $xy$
are in relation $\Theta_{0}$ if they form a square $uvyx$, where $uv$ and $xy$
are opposite edges. Then, $\Theta$ refers to the reflexive and transitive
closure of relation $\Theta_{0}$. Let $q$ be the number of equivalence classes
obtained with this relation. The classes of the equivalence relation $\Theta$
are denoted by $E_{1},\ldots,E_{q}$. Concretely, two edges $uv$ and
$u^{\prime}v^{\prime}$ belong to the same $\Theta$-class if there is a
sequence $uv=u_{0}v_{0},u_{1}v_{1},\ldots,u_{r}v_{r}=u^{\prime}v^{\prime}$
such that $u_{i}v_{i}$ and $u_{i+1}v_{i+1}$ are opposite edges of a square. We
denote by $\mathcal{E}$ the set of $\Theta$-classes:
$\mathcal{E}=\left\\{E_{1},\ldots,E_{q}\right\\}$. 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
$\lfloor\log n\rfloor$ in general.

######  Lemma 2 ($\Theta$-classes in linear time [14]).

There exists an algorithm which computes the $\Theta$-classes
$E_{1},\ldots,E_{q}$ of a median graph in linear time
$O(\left|E\right|)=O(dn)$.

In median graphs, each class $E_{i}$, $1\leq i\leq q$, is a perfect matching
cutset and its two sides $H_{i}^{\prime}$ and $H_{i}^{\prime\prime}$ verify
nice properties, that are presented below.

######  Lemma 3 (Halfspaces of $E_{i}$ [14, 28, 38]).

For any $1\leq i\leq q$, the graph $G$ deprived of edges of $E_{i}$, i.e.
$G\backslash E_{i}=(V,E\backslash E_{i})$, has two connected components
$H_{i}^{\prime}$ and $H_{i}^{\prime\prime}$, called halfspaces. Edges of
$E_{i}$ form a matching: they have no endpoint in common. Halfspaces satisfy
the following properties.

  * •

Both $H_{i}^{\prime}$ and $H_{i}^{\prime\prime}$ are convex/gated.

  * •

If $uv$ is an edge of $E_{i}$ with $u\in H_{i}^{\prime}$ and $v\in
H_{i}^{\prime\prime}$, then $H_{i}^{\prime}=W(u,v)=\left\\{x\in
V:d(x,u)<d(x,v)\right\\}$ and $H_{i}^{\prime\prime}=W(v,u)=\left\\{x\in
V:d(x,v)<d(x,u)\right\\}$.

$H_{i}^{\prime}$$H_{i}^{\prime\prime}=\partial H_{i}^{\prime\prime}$$\partial
H_{i}^{\prime}$$E_{i}$

Figure 2: A class $E_{i}$ with sets
$H_{i}^{\prime},H_{i}^{\prime\prime},\partial H_{i}^{\prime},\partial
H_{i}^{\prime\prime}$

We denote by $\partial H_{i}^{\prime}$ the subset of $H_{i}^{\prime}$
containing the vertices which are adjacent to a vertex in
$H_{i}^{\prime\prime}$: $\partial H_{i}^{\prime}=N(H_{i}^{\prime\prime})$ Put
differently, the set $\partial H_{i}^{\prime}$ is made up of vertices of
$H_{i}^{\prime}$ which are endpoints of edges in $E_{i}$. Symmetrically, set
$\partial H_{i}^{\prime\prime}$ contains the vertices of
$H_{i}^{\prime\prime}$ which are adjacent to $H_{i}^{\prime}$. We say these
sets are the boundaries of halfspaces $H_{i}^{\prime}$ and
$H_{i}^{\prime\prime}$ respectively. Figure 2 illustrates the notions of
$\Theta$-class, halfspace and boundary on a small example. In this particular
case, an halfspace is equal to its boundary: $\partial
H_{i}^{\prime\prime}=H_{i}^{\prime\prime}$. The vertices of $\partial
H_{i}^{\prime}$ are colored in blue.

######  Lemma 4 (Boundaries [14, 28, 38]).

Both $\partial H_{i}^{\prime}$ and $\partial H_{i}^{\prime\prime}$ are
convex/gated. Moreover, the edges of $E_{i}$ define an isomorphism between
$\partial H_{i}^{\prime}$ and $\partial H_{i}^{\prime\prime}$.

As a consequence, suppose $uv$ and $u^{\prime}v^{\prime}$ belong to $E_{i}$:
if $uu^{\prime}$ is an edge and belongs to class $E_{j}$, then $vv^{\prime}$
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}\in V$. The $v_{0}$-orientation of the edges of $G$ according
to $v_{0}$ is such that, for any edge $uv$, the orientation is $\vv{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 [14]).

All edges can be oriented according to any canonical basepoint $v_{0}$.

From now on, we suppose that an arbitrary basepoint $v_{0}\in V$ has been
selected and we refer automatically to the $v_{0}$-orientation when we mention
incoming or outgoing edges.

###  2.2 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}^{\prime}$. Given two
vertices $u,v\in V$, we define the set which contains the $\Theta$-classes
separating $u$ from $v$.

######  Definition 2 (Signature $\sigma_{u,v}$).

We say that the signature of the pair of vertices $u,v$, denoted by
$\sigma_{u,v}$, is the set of classes $E_{i}$ such that $u$ and $v$ are
separated in $G\backslash E_{i}$. In other words, $u$ and $v$ are in different
halfspaces of $E_{i}$.

The signature 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 $\sigma_{u,v}$.

######  Lemma 6 ([15]).

For any shortest $(u,v)$-path $P$, the edges in $P$ belong to classes in
$\sigma_{u,v}$ and, for any $E_{i}\in\sigma_{u,v}$, there is exactly one edge
of $E_{i}$ in path $P$. Conversely, a path containing at most one edge of each
$\Theta$-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
$\Theta$-class $E_{i}$ would escape temporarily from an halfspace, say w.l.o.g
$H_{i}^{\prime}$, which is convex (Lemma 3).

Definition 2 can be generalized: given a set of edges $B\subseteq E$, its
signature is the set of $\Theta$-classes represented in that set:
$\left\\{E_{i}:uv\in E_{i}\cap B\right\\}$. The signature of a path is the set
of classes which have at least one edge in this path. In this way, the
signature $\sigma_{u,v}$ is also the signature of any shortest $(u,v)$-path.
The signature of a hypercube is the set of $\Theta$-classes represented in its
edges: the cardinality of the signature is thus equal to the dimension of the
hypercube.

###  2.3 Orthogonal $\Theta$-classes and hypercubes

We present now another important notion on median graphs: orthogonality. In
[34], Kovse studied a relationship between splits which refer to the
halfspaces of $\Theta$-classes. It says that two splits
$\left\\{H_{i}^{\prime},H_{i}^{\prime\prime}\right\\}$ and
$\left\\{H_{j}^{\prime},H_{j}^{\prime\prime}\right\\}$ are incompatible if the
four sets $H_{i}^{\prime}\cap H_{j}^{\prime}$, $H_{i}^{\prime\prime}\cap
H_{j}^{\prime}$, $H_{i}^{\prime}\cap H_{j}^{\prime\prime}$, and
$H_{i}^{\prime\prime}\cap H_{j}^{\prime\prime}$ are nonempty. Another
definition was proven equivalent to this one.

######  Definition 3 (Orthogonal $\Theta$-classes).

We say that classes $E_{i}$ and $E_{j}$ are orthogonal ($E_{i}\perp E_{j}$) if
there is a square $uvyx$ in $G$, where $uv,xy\in E_{i}$ and $ux,vy\in E_{j}$.

Indeed, classes $E_{i}$ and $E_{j}$ are orthogonal if and only if the splits
produced by their halfspaces are incompatible.

######  Lemma 7 (Orthogonal$\Leftrightarrow$Incompatible [15]).

Given two $\Theta$-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 $\left\\{H_{i}^{\prime},H_{i}^{\prime\prime}\right\\}$ and
$\left\\{H_{j}^{\prime},H_{j}^{\prime\prime}\right\\}$ are incompatible,

  * •

The four sets $\partial H_{i}^{\prime}\cap\partial H_{j}^{\prime}$, $\partial
H_{i}^{\prime\prime}\cap\partial H_{j}^{\prime}$, $\partial
H_{i}^{\prime}\cap\partial H_{j}^{\prime\prime}$, and $\partial
H_{i}^{\prime\prime}\cap\partial H_{j}^{\prime\prime}$ 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}\subseteq H_{j}$ for some
$H_{i}\in\left\\{H_{i}^{\prime},H_{i}^{\prime\prime}\right\\}$ and
$H_{j}\in\left\\{H_{j}^{\prime},H_{j}^{\prime\prime}\right\\}$.

We pursue with a property on orthogonal $\Theta$-classes: if two edges of two
orthogonal classes $E_{i}$ and $E_{j}$ are incident, they belong to a common
square.

######  Lemma 8 (Squares [12, 15]).

Let $xu\in E_{i}$ and $uy\in 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 $\Theta$-classes which
are pairwise orthogonal.

######  Definition 4 (Pairwise Orthogonal Family).

We say that a set of classes $X\subseteq\mathcal{E}$ is a Pairwise Orthogonal
Family (POF for short) if for any pair $E_{j},E_{h}\in X$, we have $E_{j}\perp
E_{h}$.

The empty set is considered as a POF. We denote by $\mathcal{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 $\Theta$-classes
of a median graph form a POF if and only if the graph is a hypercube of
dimension $\log n$ [34, 35]. Secondly, the next lemma precises the
relationship between POFs and hypercubes.

######  Lemma 9 (POFs adjacent to a vertex [15]).

Let $X$ be a POF, $v\in V$, and assume that for each $E_{i}\in 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
$\Theta$-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 [7, 9, 34]).

Consider an arbitrary canonical basepoint $v_{0}\in V$ and the
$v_{0}$-orientation for the median graph $G$. Given a vertex $v\in V$, let
$N^{-}(v)$ be the set of edges going into $v$ according to the
$v_{0}$-orientation. Let $\mathcal{E}^{-}(v)$ be the classes of the edges in
$N^{-}(v)$. The following propositions are true:

  * •

For any vertex $v\in V$, $\mathcal{E}^{-}(v)$ is a POF. Moreover, vertex $v$
and the edges of $N^{-}(v)$ belong to an induced hypercube formed by the
classes $\mathcal{E}^{-}(v)$. Hence,
$\left|\mathcal{E}^{-}(v)\right|=\left|N^{-}(v)\right|\leq d$.

  * •

For any POF $X$, there is an unique vertex $v_{X}$ such that
$\mathcal{E}^{-}(v_{X})=X$. Vertex $v_{X}$ is the closest-to-$v_{0}$ vertex
$v$ such that $X\subseteq\mathcal{E}^{-}(v)$.

  * •

The number of POFs in $G$ is equal to the number $n$ of vertices:
$n=\left|\mathcal{L}\right|$.

$E_{1}$$E_{2}$$E_{3}$$E_{4}$$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$\begin{array}[]{|c||c|c|c|c|}\hline\cr\mbox{Vertex}&v_{0}&v_{1}&v_{2}&v_{3}\\\
\hline\cr\mbox{POF}&\emptyset&\left\\{E_{3}\right\\}&\left\\{E_{1}\right\\}&\left\\{E_{1},E_{3}\right\\}\\\
\hline\cr\hline\cr\mbox{Vertex}&v_{4}&v_{5}&v_{6}&v_{7}\\\
\hline\cr\mbox{POF}&\left\\{E_{4}\right\\}&\left\\{E_{2}\right\\}&\left\\{E_{2},E_{3}\right\\}&\left\\{E_{2},E_{4}\right\\}\\\
\hline\cr\end{array}$

Figure 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
$\Theta$-class. For example, $v_{1}v_{3}\in E_{1}$. We associate with any POF
$X$ of $G$ the vertex $v_{X}$ satisfying $\mathcal{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 $\Theta$-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 [9, 34]. 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 4(a) 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 $\mathcal{E}^{-}(v)$.

$E_{i}$$E_{j}$$E_{h}$$v$

(a) The hypercube “induced” by the edges incoming into a vertex (its
antibasis).

$E_{i}$$E_{h}$$E_{j}$$\partial H_{i}^{\prime\prime}\cap\partial
H_{j}^{\prime\prime}$$v^{\prime}$$v$$Q^{\prime}$$Q$

(b) A POF signing at least two hypercubes $Q$ and $Q^{\prime}$ is not maximal.

Figure 4: Properties of POFs

Number of hypercubes. We remind a formula establishing a relationship between
the number of POFs and the number of hypercubes in the literature. Let
$\alpha(G)$ (resp. $\beta(G)$) be the number of hypercubes (resp. POFs) in
$G$. Let $\beta_{i}(G)$ be the number of POFs of cardinality $i\leq d$ in $G$.
According to [9, 34], we have:

$\alpha(G)=\sum_{i=0}^{d}2^{i}\beta_{i}(G)$ (1)

Equation (1) produces a natural upper bound for the number of hypercubes.

######  Lemma 11 (Number of hypercubes).

$\alpha(G)\leq 2^{d}n$.

Value $\alpha(G)$ consider 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 $\widehat{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)$: $\widehat{N}\subseteq 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 $\Theta$-classes
$\widehat{\mathcal{E}}$ of the edges in $\widehat{N}$ (its signature).

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

######  Lemma 12 (Enumeration of hypercubes [15]).

We can enumerate all triplets $(v,u,\widehat{\mathcal{E}})$, where $v$ is the
anti-basis of a hypercube $Q$, $u$ its basis, and $\widehat{\mathcal{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^{\prime})$, then any triplet
$(v,u,\widehat{\mathcal{E}})$ containing $v$ appears before any triplet
$(v^{\prime},u^{\prime},\widehat{\mathcal{E}}^{\prime})$ containing
$v^{\prime}$.

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 $\Theta$-classes and their orthogonality relationship (for
each $E_{i}$, the set of $\Theta$-classes orthogonal to $E_{i}$) in linear
time, and the set of hypercubes with its basis, anti-basis and signature in
$\tilde{O}(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\supsetneq 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 $\mathcal{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\supsetneq X_{Q}$. As $Y$
is a POF, there is a vertex $v_{Y}\in V$ satisfying
$\mathcal{E}^{-}(v_{Y})=Y$. Similarly, we denote by $v_{X}$ the vertex such
that $\mathcal{E}^{-}(v_{X})=X_{Q}$. Both $v_{X}$ and $v_{Y}$ belong to the
boundary of any $\Theta$-class of $X_{Q}$ (the one which is the farthest from
$v_{0}$). In brief,

$v_{X},v_{Y}\in\bigcap_{E_{i}\in X_{Q}}\partial H_{i}^{\prime\prime}$ (2)

As every $\partial H_{i}^{\prime\prime}$ 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 $\bigcap_{X_{Q}}\partial
H_{i}^{\prime\prime}$. Let $(v_{X},z)$ be the first edge of this path and
$E_{j}$ the $\Theta$-class of this edge. Each $\Theta$-class form an
isomorphism between its two boundaries (Lemma 4): as
$z\in\bigcap_{X_{Q}}\partial H_{i}^{\prime\prime}$, there is a hypercube
isomorphic to $Q$ in the boundary of $E_{j}$ containing $z$. Therefore, there
is a hypercube of dimension $\left|X_{Q}\right|+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^{\prime}\neq Q$
such that $X_{Q}=X_{Q^{\prime}}$. Then, the set $\bigcap_{X_{Q}}\partial
H_{i}^{\prime\prime}$ contains at least two elements: the anti-bases of
hypercubes $Q$ and $Q^{\prime}$. Using the same argument as above, we can put
in evidence an edge with two endpoints in $\bigcap_{X_{Q}}\partial
H_{i}^{\prime\prime}$. The $\Theta$-class of this edge is thus orthogonal of
any class $E_{i}$ of $X_{Q}$ which defines an isomorphism between $\partial
H_{i}^{\prime}$ and $\partial H_{i}^{\prime\prime}$. 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 $\mathcal{E}^{-}(v)=X$ according to Lemma 10. In
summary, any maximal POF $X$ can be associated with an unique hypercube of
signature $X$. ∎

Figure 4(b) illustrates this proof with two squares $Q$ and $Q^{\prime}$ with
the same signature $\left\\{E_{i},E_{h}\right\\}$. 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.

##  3 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.

###  3.1 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 [10]).

The simplex graph $K(G)=(V_{K},E_{K})$ of $G=(V,E)$ is made up of the vertex
set $V_{K}=\left\\{C\subseteq V:C~{}\emph{induced complete graph
of}~{}G\right\\}$ and the edge set $E_{K}=$
$\left\\{(C,C^{\prime}):C,C^{\prime}\in V_{K},C\subsetneq
C^{\prime},\left|C^{\prime}\right|-\left|C\right|=1\right\\}$.

Observe that the empty clique of $G$ also corresponds to a vertex
$v_{\emptyset}$ in $K(G)$. Therefore $v_{\emptyset}$ has degree
$n=\left|V\right|$ 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 [6, 13]. 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).

$1$$2$$3$$4$$5$

$\emptyset$$\left\\{1\right\\}$$\left\\{2\right\\}$$\left\\{3\right\\}$$\left\\{4\right\\}$$\left\\{5\right\\}$$\left\\{1,2\right\\}$$\left\\{2,3\right\\}$$\left\\{3,4\right\\}$$\left\\{4,5\right\\}$$\left\\{1,5\right\\}$

Figure 5: A cycle $C_{5}$ and its simplex graph $K(C_{5})$

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}\in V(G)$ such that each $\Theta$-class of $G$ is
adjacent to $v_{0}$, i.e. $\forall 1\leq i\leq q,\exists v_{i}\in
V(G),v_{0}v_{i}\in E_{i}$.

(3)

There is a vertex $v_{0}\in V(G)$ contained in any maximal hypercube of $G$.

###### Proof.

(2)$\Leftrightarrow$(3). Assume each $\Theta$-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
$\Theta$-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 $\Theta$-class belongs to at least one maximal POF,
then each $\Theta$-class is necessarily adjacent to $v_{0}$.

(2)$\Rightarrow$(1). We consider a median graph $G$ such that all
$\Theta$-classes are adjacent to $v_{0}$. Our objective is to prove that there
exists $G^{\prime}$ such that $G=K(G^{\prime})$. Let $G^{\prime}$ be the graph
where its vertices represent the $\Theta$-classes of $G$ and two of them are
connected by an edge if the $\Theta$-classes are orthogonal. In this way,
every clique of $G^{\prime}$ (even the empty one) corresponds to a POF of $G$.
For any POF $X$ of $G$, its $\Theta$-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^{\prime}$.
Conversely, according to the $v_{0}$-orientation, each vertex admits its own
set of incoming $\Theta$-classes which forms a POF (Lemma 10). Therefore, we
can associate to each vertex of $G$ a clique of $G^{\prime}$.

Then, two vertices $u,v$ of $G$ are adjacent if and only if
$\mathcal{E}^{-}(v)=\mathcal{E}^{-}(u)\cup\left\\{E_{i}\right\\}$, for some
class $E_{i}$. On one hand, suppose $uv\in E_{i}$. Assume that there exists
$E_{j}\in\mathcal{E}^{-}(u)\backslash\mathcal{E}^{-}(v)$. Then, $E_{j}$ is
parallel to $E_{i}$, otherwise $E_{j}\in\mathcal{E}^{-}(v)$ (Lemma 8). This is
a contradiction: as $H_{i}^{\prime\prime}\subsetneq H_{j}^{\prime\prime}$,
$E_{i}$ cannot be adjacent to $v_{0}$. Moreover, if
$E_{h}\in\mathcal{E}^{-}(v)\backslash\mathcal{E}^{-}(u)$, $h\neq i$, then
$E_{h}$ is necessarily incoming into $u$ because of Lemma 8, as $E_{h}$ and
$E_{i}$ are orthogonal. So,
$\mathcal{E}^{-}(v)\backslash\mathcal{E}^{-}(u)=\left\\{E_{i}\right\\}$. On
the other hand, if
$\mathcal{E}^{-}(v)=\mathcal{E}^{-}(u)\cup\left\\{E_{i}\right\\}$, let
$v^{\prime}$ be the vertex such that $v^{\prime}v\in E_{i}$. Again, Lemma 8
implies that all $\Theta$-classes incoming into $v$ are also incoming into
$v^{\prime}$, so $\mathcal{E}^{-}(u)\subseteq\mathcal{E}^{-}(v^{\prime})$.
Furthermore, if there is some $E_{j}\notin\mathcal{E}^{-}(u)$ incoming into
$v^{\prime}$, then it should be parallel to $E_{i}$, a contradiction. Hence,
$v^{\prime}=u$.

(1)$\Rightarrow$(2). Assume that $G=K(G^{\prime})$: we denote by
$v_{\emptyset}$ the vertex representing the empty clique. By contradiction, we
suppose that there exists a $\Theta$-class which is not adjacent to
$v_{\emptyset}$: we denote it by $E_{1}$. We consider the
$v_{\emptyset}$-orientation of the graph. As $\left\\{E_{1}\right\\}$ is a
POF, there is necessarily one vertex $v_{1}$ with only one incoming edge
belonging to $E_{1}$. As $v_{1}\neq v_{\emptyset}$, vertex $v_{1}$ represents
a clique of $G^{\prime}$ of size at least 1. If $v_{1}$ represents a clique of
size exactly 1, then it is adjacent to $v_{\emptyset}$ because only one
element differ between the cliques represented by both $v_{\emptyset}$ 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^{\prime})$, each $\Theta$-class of $G$ is adjacent to
$v_{\emptyset}$. ∎

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
$\Theta$-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
$\left\\{\left\\{E_{1},E_{2}\right\\},\left\\{E_{2},E_{3}\right\\},\left\\{E_{3},E_{1}\right\\}\right\\}$:
it would produce a simplex graph with 3 squares with basis $v_{0}$ and sharing
pairwise an edge. This graph is $Q_{3}^{-}$ (the 3-cube minus a vertex) and is
not median. The collection implies that $E_{1},E_{2},E_{3}$ are pairwise
orthogonal, so $\left\\{E_{1},E_{2},E_{3}\right\\}$ 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 $\Theta$-classes which are all pairwise
parallel. For any vertex of $P_{4}$, there exists a $\Theta$-class which is
not adjacent to it.

The proof (2)$\Rightarrow$(1) reveals the reverse application of $K$.

######  Definition 6 (Crossing graphs [10, 31]).

Let $G$ be a median graph. Its crossing graph $G^{\\#}$ is the graph obtained
by considering $\Theta$-classes as its vertices and such that two
$\Theta$-classes are adjacent if they are orthogonal.

Restricted to simplex graphs, this transformation is the reverse of $K$:
indeed, as stated in [31], $G=K(G)^{\\#}$. The clique number of $G^{\\#}$ is
exactly the dimension of median graph $G$. For example, the crossing graph of
a cube-free 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
$\sigma_{v_{0},u}=\mathcal{E}^{-}(u)$. This is a consequence of Theorem 2: all
$\Theta$-classes of $\mathcal{E}^{-}(u)$ are adjacent to $v_{0}$, so $v_{0}$
is the basis of the hypercube with signature $\mathcal{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)=\left|\mathcal{E}^{-}(u)\right|$.

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)=\mbox{{ecc}}(u)$.

######  Lemma 13.

Let $u,v\in V(G)$ such that $d(u,v)=\mbox{{ecc}}(u)$. Then, $v_{0}\in 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 $\Theta$-classes of $G$ separating them, so
$d(u,v)=\left|\mathcal{E}^{-}(u)\bigtriangleup\mathcal{E}^{-}(v)\right|$. Let
$w$ be the vertex of $G$ such that
$\mathcal{E}^{-}(w)=\mathcal{E}^{-}(v)\backslash\mathcal{E}^{-}(u)$. If
$\mathcal{E}^{-}(u)\cap\mathcal{E}^{-}(v)\neq\emptyset$, then
$d(u,w)=\left|\mathcal{E}^{-}(u)\bigtriangleup\mathcal{E}^{-}(w)\right|=\left|\mathcal{E}^{-}(u)\right|+\left|\mathcal{E}^{-}(w)\right|>\left|\mathcal{E}^{-}(u)\backslash\mathcal{E}^{-}(v)\right|+\left|\mathcal{E}^{-}(v)\backslash\mathcal{E}^{-}(u)\right|=d(u,v)$.
So, $d(u,w)>\mbox{{ecc}}(u)$, a contradiction. ∎

$E_{i}$$v_{0}$$m$$u$$v$$w$

Figure 6: Illustration of the contradiction in the proof of Lemma 13.

Figure 6 shows a simple example with $m=m(u,v,v_{0})\neq v_{0}$ and
$d(v_{0},m)=1$. The edges are oriented according to the $v_{0}$-orientation.
The $\Theta$-class $E_{i}$ in $\sigma_{v_{0},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 $\partial H_{i}^{\prime}$.

Two vertices $u,v$ forming a diametral pair cannot share a common incoming
$\Theta$-class $E_{i}$, in other words
$\mathcal{E}^{-}(u)\cap\mathcal{E}^{-}(v)=\emptyset$, otherwise
$m=m(u,v,v_{0})\in I(u,v)\subseteq H_{i}^{\prime\prime}$ and $v_{0}\in
H_{i}^{\prime}$. Moreover, the distance $d(u,v)$ is exactly
$\left|\mathcal{E}^{-}(u)\right|+\left|\mathcal{E}^{-}(v)\right|$ because
$\left|\mathcal{E}^{-}(u)\right|=d(v_{0},u)$ and
$\left|\mathcal{E}^{-}(v)\right|=d(v_{0},v)$. So, determining the diameter of
a simplex graph $G$ is equivalent to maximizing the sum
$\left|X\right|+\left|Y\right|$, where $X$ and $Y$ are two POFs of $G$ that
are disjoint. Computing the diameter is equivalent to find the largest pair of
disjoint cliques in the crossing graph $G^{\\#}$. Similarly, the eccentricity
of a vertex $u$ is exactly the size
$\left|\mathcal{E}^{-}(u)\right|+\left|\mathcal{E}^{-}(v)\right|$ of the
largest pair of disjoint POFs $(\mathcal{E}^{-}(u),\mathcal{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 $\mbox{{op}}(X)$
the opposite of $X$, i.e. the POF $Y$ disjoint from $X$ with the maximum
cardinality.

$\mbox{{op}}(X)=\operatorname*{argmax}_{Y\cap X=\emptyset}\left|Y\right|.$

With this definition, the eccentricity of a vertex $u$, if we fix
$X_{u}=\mathcal{E}^{-}(u)$, is written
$\mbox{{ecc}}(u)=\left|X_{u}\right|+\left|\mbox{{op}}(X_{u})\right|$. Hence,
the diameter of the simplex graph $G$ can be written as the size of the
largest pair POF-opposite:
$\mbox{{diam}}(G)=\max_{X\in\mathcal{L}}(\left|X\right|+\left|\mbox{{op}}(X)\right|)$.

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 $\mbox{{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
$\omega:\mathcal{L}\rightarrow\mathbb{N}^{+}$.

Output: For each POF $X$, its weighted opposite $Y$ maximizing $\omega(Y)$
such that $X\cap Y=\emptyset$.

Obviously, OPP is a special case of WOPP when $\omega$ 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
[15].

###  3.2 Quasilinear algorithm for all eccentricities in simplex graphs

We propose an algorithm solving WOPP in quasilinear time $\tilde{O}(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
$\omega:\mathcal{L}\rightarrow\mathbb{N}^{+}$. The algorithm is presented in
Sections 3.2.1 and 3.2.2 and its analysis in Section 3.2.3.

####  3.2.1 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
$\mathcal{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 [27, 39]. It consists in successive partitionings of a
collection of sets.

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

We denote by $\mathcal{L}\left[E_{i}\right]$ the adjacency list of
$\Theta$-class $E_{i}$, i.e. the list of POFs in $\mathcal{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\left|\mathcal{L}\right|$.

We sort the POFs in $\mathcal{L}$ in function of their weights $\omega(L)$ in
the decreasing order. This takes $O(n\log n)$. We denote by $\tau_{\omega}$
this ordering. Let $L_{0}$ be the maximum-weighted POF in $\mathcal{L}$, in
other words the first POF in ordering $\tau_{\omega}$.

The description of the construction of $T$ by partition refinement begins. We
assign an arbitrary ordering to the $\Theta$-classes which are in $L_{0}$, for
example based on their index. Let $E_{i_{1}},E_{i_{2}},\ldots,E_{i_{r}}$ be
the classes of $L_{0}$ ordered, $\left|L_{0}\right|=r$. First, we split
$\mathcal{L}$ in two sets: one with POFs containing $E_{i_{1}}$, the other
with POFs which do not contain $E_{i_{1}}$. In brief, we obtain
$\mathcal{L}\left[E_{i_{1}}\right]$ and its complementary. Second, we split
each of these two sets regarding $\Theta$-class $E_{i_{2}}$: on one side the
POFs containing $E_{i_{2}}$, on the other side POFs without $E_{i_{2}}$. We
pursue in this way with all classes of $L_{0}$. At the end, there are at most
$2^{\left|L_{0}\right|}$ sets in the partition.

Until now, we obtained the top $r$ depths 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 $\mathcal{L}$. Let $\Omega$ be the
function indicating the sets represented by each node $a\in V(T)$. We have
$\Omega(a_{0})=\mathcal{L}$. For any $a\in T$, its index $L_{a}$ is defined as
the maximum-weighted POF of its universe $\Omega(a)$. So, $L_{a_{0}}=L_{0}$.
The root $a_{0}$ has two children, one representing
$\mathcal{L}\left[E_{i_{1}}\right]$ and the other one its complementary as
they are the result of a partition refinement from $E_{i_{1}}$. The edges
connecting $a_{0}$ and its children are indexed by $+E_{i_{1}}$ and
$-E_{i_{1}}$ respectively.

We denote by $R(a)$ the set of edge indices of the simple path from $a$ to the
root $a_{0}$. For example, for node $a$ with an universe $\Omega(a)$ being the
set of POFs which contain $E_{i_{2}}$ but not $E_{i_{1}}$, we have
$R(a)=\left\\{E_{i_{1}},E_{i_{2}}\right\\}$. We write $R(a)=R^{+}(a)\cup
R^{-}(a)$, where $R^{+}(a)$ contains indices with boolean true, while
$R^{-}(a)$ contains indices with boolean false. In this example,
$R^{+}(a)=\left\\{E_{i_{2}}\right\\}$ and
$R^{-}(a)=\left\\{E_{i_{1}}\right\\}$. Set $R^{+}(a)$ is a POF: it contains
$\Theta$-classes which are pairwise orthogonal, otherwise $R^{+}(a)$ would not
be the subset of a POF belonging to $\mathcal{L}$.

We pursue the construction of $T$. For each leaf $a$ of the current tree, we
execute the following process: we only consider the $\Theta$-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 $\Omega(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 $\Theta$-classes of $L_{0}$. In
Figure 7(a), we represent some nodes $a$ of this block and their index $L_{a}$
with $\left|L_{0}\right|=3$: $i_{1}=i$, $i_{2}=j$, and $i_{3}=\ell$. The
leaves of this block both belong to the top block and are the roots of another
block below this one.

$\left\\{E_{i},E_{j},E_{\ell}\right\\}$$\left\\{E_{j},E_{\ell},E_{q}\right\\}$$\left\\{E_{j},E_{\ell},E_{q}\right\\}$$\left\\{E_{j},E_{r}\right\\}$$a_{0}$$a_{1}$$a_{2}$$a_{3}$$-E_{i}$$+E_{i}$$-E_{j}$$+E_{j}$$+E_{\ell}$$-E_{\ell}$

(a) Some nodes of $T$ obtained with the partition refinement over $L_{0}$

$T_{m}^{(2)}$$a_{0}$$a_{1}$$a_{2}$$a_{3}$$a$

(b) Some blocks of $T$: all blocks of layer 0 and 1, one block of layer 2.
Node $a$ has layer 2.

Figure 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
$\Theta$-classes of $G$ ($W=\mathcal{E}$), the collection is made up of the
POFs outgoing from $m$ ($\mathcal{S}=\mathcal{L}$) and the ordering of the
sets come from the POFs weights ($\tau=\tau_{\omega}$). Each while loop (line
1) 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
$\mathcal{P}$, say $\Omega(a)$. Then, we consider the $\Theta$-classes of
$L_{a}$ which have not been locally visited, i.e. which do not belong to
$R^{+}(a)$ (line 1). For each of these classes $E_{j}$, we refine the non-
singleton $\Omega(a)$: we split it successively with the POFs containing
$E_{j}$ and the POFs not containing $E_{j}$ (line 1).

1 Input: ground set $W=\left\\{w_{1},\ldots,w_{q}\right\\}$, collection
$\mathcal{S}=\left\\{S_{1},\ldots,S_{N}\right\\}$, $S_{i}\subseteq W$ for any
$1\leq i\leq N$, and an ordering $\tau$ of $\mathcal{S}$.

2 Output: An ordered partition $\mathcal{P}$ of $\mathcal{S}$ made up of
singletons.

3 Initialize $\mathcal{P}\leftarrow\left\\{\mathcal{S}\right\\}$, partition
with a single set;

4 while  _there exists a part of $\mathcal{P}$ which is not a singleton _ do

5 $Q\leftarrow$ first non-singleton of the ordered partition $\mathcal{P}$;

6 $A\leftarrow$ first element of $Q$ according to $\tau$;

7for  _every $w_{j}\in A$ non locally visited_ do

8 Substitute $Q$ in $\mathcal{P}$ by
$\textsf{Refine}(Q,\left\\{w_{j}\right\\})$;

9 endfor

end while

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 $\mathcal{S}$.

######  Lemma 14 (Execution time of OIPR [27]).

Let $M(w_{j})$ be the number of sets $S_{i}\in\mathcal{S}$ such that $w_{j}\in
S_{i}$. Then, OIPR runs in $O(\sum_{j=1}^{q}M(w_{j}))$.

In our context, values $M(w_{j})$ are the sizes of adjacency lists
$\mathcal{L}\left[E_{j}\right]$. We explained above why the total size of
these adjacency lists could not exceed $dn$.

######  Corollary 2.

OIPR applied with $W=\mathcal{E}$, $\mathcal{S}=\mathcal{L}$ and
$\tau=\tau_{\omega}$ runs in $O(n(d+\log n))$.

###### Proof.

The time needed to sort all POFs according to their weights, i.e. in order
$\tau_{\omega}$, 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 $\Omega(a)$ with some
$\Theta$-class $E_{j}=E\left[a\right]$: one represents the elements of
$\Omega(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 $\mathcal{L}$ is
finite, $T$ is too. Its depth is at most $n=\left|\mathcal{L}\right|$. 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\geq 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\in V(T)$ may admit only one child. This situation occurs when
$E\left[a\right]$ is not orthogonal to at least one class of $R^{+}(a)$.
Indeed, each POF of $\Omega(a)$ contains all $\Theta$-classes of $R^{+}(a)$:
if $R^{+}(a)\cup\left\\{E\left[a\right]\right\\}$ is not a POF, then there is
no POF superset of $R^{+}(a)\cup\left\\{E\left[a\right]\right\\}$.

For any node $a$, we store its universe $\Omega(a)$. With the doubly linked
list data structure for each partitioning, we can preserve the original
ordering of the POFs. Consequently, in all sets $\Omega(a)$, the POFs are
sorted in function of their weight. For any $a\in V(T)$, the maximum-weighted
POF of $\Omega(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 $\Omega(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$, such as the execution of the partitioning.

####  3.2.2 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\in V(T)$ and a POF $X$ such
that (i) $X\cap R(a)=\emptyset$ and (ii) $X\cup R^{+}(a)\in\mathcal{L}$.

The existence of a constraint pair $(a,X)$ implies that no class $X$ is
present in the edge indices from $a_{0}$ to $a$ in $T$. Moreover, each
$\Theta$-class of $X$ is orthogonal to all $\Theta$-classes of $R^{+}(a)$. We
denote by $\mathcal{C}$ the set of constraint pairs. Let $\mathcal{C}^{(j)}$
be the set of constraint pairs $(a,X)$ such that $a\in T^{(j)}$: we have
$\mathcal{C}^{(j)}\subseteq\mathcal{C}^{(j+1)}\subseteq\mathcal{C}$.

For any constraint pair $(a,X)$, we denote by $h(a,X)$ a POF $X^{*}$ disjoint
from $X$ in $\Omega(a)$ with the maximum weight. For any POF
$L\in\mathcal{L}$, the POF $h(a_{0},L)$ is an opposite of $L$ because
$\Omega(a_{0})=\mathcal{L}$, so we can write, according to Definition 7,
$h(a_{0},L)=\mbox{{op}}(L)$. Observe that any pair $(a_{0},L)$ is a constraint
pair as $R(a_{0})=\emptyset$. 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\left[a\right]$ (resp. $-E\left[a\right]$) in $T$
(Figure 8). We define the set $\mathcal{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^{\prime},X^{\prime})$, where
$(a^{\prime},X^{\prime})\in\mathcal{C}(a,X)$. The construction of set
$\mathcal{C}(a,X)$ is described below. We distinguish four cases: A, B, C, and
D.

$\Omega(a),L_{a},R(a)$$\Omega(a^{-}),L_{a^{-}},R(a^{-})$$\Omega(a^{+}),L_{a^{+}},R(a^{+})$$a$$a^{-}$$a^{+}$$-E\left[a\right]$$+E\left[a\right]$

Figure 8: Nodes $a$, $a^{+}$ and $a^{-}$ in tree $T$.

  * •

Case A. No class of $X$ is in $L_{a}$, i.e. $L_{a}\cap X=\emptyset$.
Otherwise, see next cases.

As $L_{a}$ is the maximum-weighted POF in $\Omega(a)$ and $L_{a}\cap
X=\emptyset$, we have $h(a,X)=L_{a}$. No recursive call is needed:
$\mathcal{C}(a,X)=\emptyset$.

A special case of Case A is when $\Omega(a)$ is a singleton:
$\Omega(a)=R^{+}(a)$. We know from Definition 10 that $R^{+}(a)\cap
X=\emptyset$.

  * •

Case B. Class $E\left[a\right]$ belongs to $X$: $E\left[a\right]\in X$.
Otherwise, see next cases.

As $R(a^{-})=R(a)\cup\left\\{E\left[a\right]\right\\}$,
$(a^{-},X\backslash(E\left[a\right]))$ is a constraint pair (Definition 10):
$R(a^{-})\cap(X\backslash(E\left[a\right]))=\emptyset$ and
$R^{+}(a^{-})=R^{+}(a)$ is orthogonal to all $\Theta$-classes of set
$X\backslash(E\left[a\right])\subsetneq X$.

We fix $\mathcal{C}(a,X)$ as a singleton containing
$(a^{-},X\backslash(E\left[a\right]))$:
$\mathcal{C}(a,X)=\left\\{(a^{-},X\backslash(E\left[a\right]))\right\\}$.

  * •

Case C. Set $E\left[a\right]\cup X$ is a POF: $E\left[a\right]\cup
X\in\mathcal{L}$.

As $E\left[a\right]\notin X$, we have $X\cap R(a^{+})=X\cap
R(a^{-})=\emptyset$. First, $R^{+}(a^{-})=R^{+}(a)$, so $X\cup R^{+}(a^{-})$
is a POF and $(a^{-},X)\in\mathcal{C}$. Second, $R^{+}(a^{+})=R^{+}(a)\cup
E\left[a\right]$: as $E\left[a\right]$ is orthogonal to all $\Theta$-classes
of $X$, $R^{+}(a^{+})\cup X$ is a POF and $(a^{+},X)\in\mathcal{C}$.

These two constraint pairs are the elements of $\mathcal{C}(a,X)$:
$\mathcal{C}(a,X)=\left\\{(a^{+},X),(a^{-},X)\right\\}$.

  * •

Case D. Set $E\left[a\right]\cup X$ is not a POF: $E\left[a\right]\cup
X\notin\mathcal{L}$.

Let $X_{|E[a]}\subsetneq X$ be the $\Theta$-classes of $X$ which are
orthogonal to $E\left[a\right]$. Pair $(a^{-},X)$ is a constraint pair, using
the same arguments than in Case C. We verify whether another pair
$(a^{+},X_{|E[a]})\in\mathcal{C}$. As $X_{|E[a]}\subsetneq X$ and
$E\left[a\right]\notin X$, we have $R(a^{+})\cap X_{|E[a]}=\emptyset$.
Furthermore, $X_{|E[a]}\cup R^{+}(a)$ is a POF because $(a,X)$ is a constraint
pair and $X_{|E[a]}\cup E\left[a\right]$ is a POF by definition, so
$X_{|E[a]}\cup R^{+}(a^{+})$ is a POF.

We fix $\mathcal{C}(a,X)=\left\\{(a^{-},X),(a^{+},X_{|E[a]})\right\\}$.

Observe that when $(a^{\prime},X^{\prime})\in\mathcal{C}(a,X)$, then $a$ is a
parent of $a^{\prime}$ in $T$. Moreover, $X^{\prime}\subseteq X$. The size of
all sets of recursive calls $\mathcal{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^{\prime},X^{\prime})$ satisfying
$(a^{\prime},X^{\prime})\in\mathcal{C}(a,X)$.

######  Theorem 4.

Let $(a,X)\in\mathcal{C}$. If $\mathcal{C}(a,X)=\emptyset$ (Case A), $h(a,X)$
is equal to $L_{a}$. Otherwise:

$h(a,X)=\operatorname*{argmax}_{h(a^{\prime},X^{\prime})\mbox{~{}s.t.~{}}(a^{\prime},X^{\prime})\in\mathcal{C}(a,X)}\omega\left(h(a^{\prime},X^{\prime})\right)$
(3)

###### Proof.

The justification for Case A was evoked above: as $L_{a}\cap X=\emptyset$ and
$L_{a}$ is the maximum-weighted POF of $\Omega(a)$, then $h(a,X)=L_{a}$.

In Case B, $E\left[a\right]\in X$. Recall that
$\mathcal{C}(a,X)=\left\\{(a^{-},X\backslash E\left[a\right])\right\\}$ in
this case. POF $h(a,X)$, which is disjoint from $X$, cannot contain class
$E\left[a\right]$. As a consequence, $h(a,X)$ belongs to $\Omega(a^{-})$ which
is made up of the POFs of $\Omega(a)$ without $E\left[a\right]$. Moreover,
$h(a,X)$ does not contain any class of $X\backslash E\left[a\right]$. We have:
$h(a,X)=h(a^{-},X\backslash E\left[a\right])$.

In Case C, we assume that $E\left[a\right]\cup X$ is a POF. As
$E\left[a\right]\notin X$, $h(a,X)$ can be either in $\Omega(a^{-})$ or in
$\Omega(a^{+})$. POFs $h(a^{-},X)$ and $h(a^{+},X)$ are respectively the
maximum-weighted POFs of $\Omega(a^{-})$ and $\Omega(a^{+})$ without any class
of $X$. Equation (3) holds as
$\mathcal{C}(a,X)=\left\\{(a^{-},X),(a^{+},X)\right\\}$.

In Case D, we assume that $E\left[a\right]\cup X$ is not a POF. As in Case C,
$E\left[a\right]\notin X$, so $(a^{-},X)$ is a constraint pair. If $h(a,X)$
belongs to $\Omega(a^{-})$, then it is $h(a^{-},X)$. Moreover,
$(a^{+},X_{|E[a]})\in\mathcal{C}$ and we prove that if $h(a,X)$ belongs to
$\Omega(a^{+})$, it is $h(a^{+},X_{|E[a]})$. Let $E_{h}$ be a $\Theta$-class
of $X\backslash X_{|E[a]}$. Classes $E_{h}$ and $E\left[a\right]$ are
parallel, otherwise $E_{h}$ would belong to $X_{|E[a]}$. All POFs of set
$\Omega(a^{+})$ contain $E\left[a\right]$, so none of them can contain
$E_{h}$: it would be contradictory with the non-orthogonality of these
$\Theta$-classes. In summary, no POF in $\Omega(a^{+})$ contains a
$\Theta$-class of $X\backslash X_{|E[a]}$. Therefore, determining the maximum-
weighted POF of $\Omega(a^{+})$ disjoint from $X$ is equivalent to finding the
maximum-weighted POF of $\Omega(a^{+})$ disjoint from $X_{|E[a]}$. In brief,
if $h(a,X)$ is in $\Omega(a^{+})$, it is $h(a^{+},X_{|E[a]})$. Equation (3)
holds as $\mathcal{C}(a,X)=\left\\{(a^{-},X),(a^{+},X_{|E[a]})\right\\}$. ∎

The DP algorithm consists in recursively applying Equation (3) from all
$h(a_{0},L)$, for any $L\in\mathcal{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)\in\mathcal{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)\in V(H)$ to elements in $\mathcal{C}(a,X)$.
Certain constraint pairs of $\mathcal{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 $\mbox{{op}}(L)=h(a_{0},L)$ and
$\mbox{{op}}(\widehat{L})=h(a_{0},\widehat{L})$: dotted lines mean there is a
path between two pairs.

$(a_{0},L)$$(a_{0},\widehat{L})$$(a,X)$$(a^{\prime},X^{\prime})$$(a^{\prime\prime},X^{\prime\prime})$$(\tilde{a},\tilde{X})$$\mathcal{C}(a,X)$$\mathcal{C}(a^{\prime},X^{\prime})$

Figure 9: Some vertices of the DAG $H$

We observe that the constraint pairs of $V(H)$ are made up of nodes of
$T^{(d)}$.

######  Lemma 15.

Constraint pairs $(a,X)$ in $V(H)$ satisfy the following inequality:
$\left|X\right|\leq d-\textsf{layer}(a)$.

###### Proof.

We proceed by induction. The roots of the DAG, i.e. the constraint pairs
$(a_{0},X)$, verify this inequality, as $\textsf{layer}(a_{0})=0$.

Assume now that the ancestors of $(a,X)\in V(H)$ satisfy the inequality. We
distinguish two cases. First, suppose there is a predecessor of $(a,X)$, i.e.
a constraint pair $(a^{\prime},X^{\prime})$ and an arc going from it to
$(a,X)$, such that $\textsf{layer}(a)=\textsf{layer}(a^{\prime})+1$. We select
a pair $(\widehat{a}^{\prime},\widehat{X}^{\prime})$ in $V(H)$ which is an
ancestor of $(a^{\prime},X^{\prime})$ \- there is a directed path from
$(\widehat{a}^{\prime},\widehat{X}^{\prime})$ to $(a^{\prime},X^{\prime})$ in
$H$ \- and such that $\widehat{a}^{\prime}$ is the ancestor of $a^{\prime}$ in
$T$ which is at the top of the block $\mathcal{B}_{\widehat{a}^{\prime}}$ of
layer $\textsf{layer}(a^{\prime})$ containing $a^{\prime}$. Thus, node $a$ is
a leaf of block $\mathcal{B}_{\widehat{a}^{\prime}}$. The existence of a
directed path in $H$ from $(\widehat{a}^{\prime},\widehat{X}^{\prime})$ to
$(a,X)$ means that the recursive computation of
$h(\widehat{a}^{\prime},\widehat{X}^{\prime})$ uses the term $h(a,X)$. The POF
$L_{\widehat{a}^{\prime}}$ is not disjoint from $\widehat{X}^{\prime}$
otherwise pair $(\widehat{a}^{\prime},\widehat{X}^{\prime})$ would be a leaf
in $H$ (Case A). Let $E_{h}\in
L_{\widehat{a}^{\prime}}\cap\widehat{X}^{\prime}$. As $a$ is a leaf of the
block $\mathcal{B}_{\widehat{a}^{\prime}}$, it verifies $E_{h}\in R(a)$ by
construction of $T$. As $(\widehat{a}^{\prime},\widehat{X}^{\prime})$ is an
ancestor of $(a,X)$, then $X\subseteq\widehat{X}^{\prime}$. But $(a,X)$ is a
constraint pair and $E_{h}\in R(a)$, so
$X\subseteq\widehat{X}^{\prime}\backslash\left\\{E_{h}\right\\}$. In brief,
$\left|X\right|\leq\left|\widehat{X}^{\prime}\right|-1$. Using the induction
hypothesis, $\left|X\right|\leq
d-\textsf{layer}(\widehat{a}^{\prime})-1=d-\textsf{layer}(a)$.

Second, suppose that all predecessors $(a^{\prime},X^{\prime})$ of $(a,X)$
satisfy $\textsf{layer}(a^{\prime})=\textsf{layer}(a)$. As $X\subseteq
X^{\prime}$, $\left|X\right|\leq\left|X^{\prime}\right|\leq
d-\textsf{layer}(a^{\prime})=d-\textsf{layer}(a)$. ∎

As a consequence, for any pair $(a,X)\in 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)\subseteq\mathcal{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.

####  3.2.3 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. 1.

Construction of the tree $T^{(d)}$ with maximum layer $d$, using partition
refinement, storage of $\Omega(a)$, $L_{a}$, and $R(a)$ for each node $a$ of
$T^{(d)}$.

  2. 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 $\Omega(a),L_{a},R(a)$ for each node $a\in
V(T^{(d)})$ can be upper-bounded by $O(d^{2}n)$ because the sets $\Omega(a)$
together at some fixed depth form a partition of $\mathcal{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 $\mathcal{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 $\mathcal{C}^{(d)}$.

###### Proof.

We define a function $f:\mathcal{L}\rightarrow 2^{\mathcal{C}}$ such that, for
any $L\in\mathcal{L}$, $\left|f(L)\right|\leq d^{2}$. We show that for any
constraint pair $(a,X)\in\mathcal{C}^{(d)}$, there is a POF $Y$, $X\subseteq
Y$, such that $(a,X)\in f(Y)$. As the total number of constraint pairs
generated by $f$ is at most $d^{2}n$, we have
$\left|\mathcal{C}^{(d)}\right|\leq d^{2}n$.

\- Step 1: definition of function $f$. Our method consists in defining an
itinerary function $I:\mathcal{C}^{(d)}\rightarrow\mathcal{C}^{(d)}$, where
$(a,X)=I(a^{\prime},X^{\prime})$ implies that $X\subseteq X^{\prime}$ and $a$
is a child of $a^{\prime}$ in $T^{(d)}$. Starting from some $(a_{0},Y)$, where
$Y\in\mathcal{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)=\left\\{(a_{0},Y),I(a_{0},Y),I(I(a_{0},Y)),\ldots\right\\}$. As the
depth of $T^{(d)}$ is at most $d^{2}$, we confirm that $\left|f(Y)\right|\leq
d^{2}$.

Here is the definition of function $I$ and we verify the properties announced
above. Let $(a^{\prime},X^{\prime})\in\mathcal{C}^{(d)}$: we denote by $a^{-}$
(resp. $a^{+}$) his child which is the endpoint of edge indexed by
$-E\left[a^{\prime}\right]$ (resp. $+E\left[a^{\prime}\right]$). We
distinguish three cases: as they are similar to some Cases enumerated the
previous subsubsection, we denote them by B*, C* and D* respectively.

  * •

Case B*: $\Theta$-class $E\left[a^{\prime}\right]$ belongs to $X$, i.e.
$E\left[a^{\prime}\right]\in X$. We fix
$I(a^{\prime},X^{\prime})=(a^{-},X\backslash\left\\{E\left[a^{\prime}\right]\right\\})$.

  * •

Case C*: $E\left[a^{\prime}\right]\notin X$ and $E\left[a^{\prime}\right]\cup
X$ is a POF. We fix $I(a^{\prime},X^{\prime})=(a^{+},X)$.

  * •

Case D*: $E\left[a^{\prime}\right]\notin X$ and $E\left[a^{\prime}\right]\cup
X$ is not a POF. We fix $I(a^{\prime},X^{\prime})=(a^{-},X)$.

Any constraint pair is concerned by one of these three cases. One can see that
if $I(a^{\prime},X^{\prime})=(a,X)$ then $a$ is a child of $a^{\prime}$ and
$X\subseteq X^{\prime}$.

\- Step 2: any constraint pair is generated by $f$. We show that any
$(a,X)\in\mathcal{C}^{(d)}$ can be written as $I^{k}(a_{0},Y)$ for some POF
$Y\supseteq X$ and $0\leq k<d^{2}$. We proceed by induction on the depth of
$a$. The base case is trivial: If $\textsf{depth}(a)=0$, then $a=a_{0}$. For
any $X\in\mathcal{L}$, $(a_{0},X)\in f(X)$.

Let $(a,X)\in\mathcal{C}^{(d)}$, $a\neq a_{0}$, we assume that each constraint
pair containing an ancestor of $a$ belongs to some $f(Y)$. We distinguish
three scenarii depending on the nature of both the parent $a^{\prime}$ of $a$
and $\Theta$-class $E\left[a^{\prime}\right]$. For each scenario, we show that
there is a constraint pair $(a^{\prime},X^{\prime})$ such that
$I(a^{\prime},X^{\prime})=(a,X)$ and $X\subseteq X^{\prime}$. As
$(a^{\prime},X^{\prime})=I^{k}(a_{0},Y)$ and $X^{\prime}\subseteq Y$ by
induction, such statement implies that $(a,X)=I^{k+1}(a_{0},Y)$ and
$X\subseteq Y$, in other words $(a,X)\in f(Y)$.

  * •

Scenario 1: edge $(a^{\prime},a)$ in $T$ is indexed by
$-E\left[a^{\prime}\right]$ and $X\cup E\left[a^{\prime}\right]$ is a POF.

Let $X^{\prime}=X\cup\left\\{E\left[a^{\prime}\right]\right\\}$. We begin with
the proof that $(a^{\prime},X^{\prime})$ is a constraint pair. First, set
$R(a)$ is the union of singleton $\left\\{E\left[a^{\prime}\right]\right\\}$
with $R(a^{\prime})$, so $E\left[a^{\prime}\right]\notin R(a^{\prime})$. As
$(a,X)\in\mathcal{C}$, $X\cap R(a)=\emptyset$, so
$X\cup\left\\{E\left[a^{\prime}\right]\right\\}$ has no intersection with
$R(a^{\prime})$. In brief, $X^{\prime}\cap R(a^{\prime})=\emptyset$. Second,
as $(a,X)\in\mathcal{C}$, we affirm that any $\Theta$-class of $X$ is
orthogonal to any class of $R^{+}(a)=R^{+}(a^{\prime})$. Showing that
$E\left[a^{\prime}\right]$ is orthogonal to any class of $R^{+}(a^{\prime})$
will imply that $X^{\prime}\cup R^{+}(a^{\prime})$ is a POF. If $a^{\prime}$
is the root of some block, then $E\left[a^{\prime}\right]$ is a $\Theta$-class
of $L_{a^{\prime}}$. As $L_{a^{\prime}}$ contains all $\Theta$-classes of
$R^{+}(a^{\prime})$ by definition, this shows the orthogonality of
$E\left[a^{\prime}\right]$ with $R^{+}(a^{\prime})$. Now, assume that
$a^{\prime}$ is not the root of some block: $\mathcal{B}_{a^{\prime}}$ denotes
the block it belongs to and the root of $\mathcal{B}_{a^{\prime}}$ is written
$a^{*}\neq a^{\prime}$ (Figure 10). Node $a^{*}$ is an ancestor of
$a^{\prime}$. Set $R^{+}(a^{\prime})$ can be splitted as follows: on one hand,
the $\Theta$-classes of $R^{+}(a^{\prime})$ indexed between $a_{0}$ and
$a^{*}$, i.e. $R^{+}(a^{*})$, and on the other hand the $\Theta$-classes of
$R^{+}(a^{\prime})$ whose indices appear in the block
$\mathcal{B}_{a^{\prime}}$, i.e. $R^{+}(a^{\prime})\cap L_{a^{*}}$. Class
$E\left[a^{\prime}\right]$ belongs to $L_{a^{*}}$, otherwise $a^{\prime}$
would be the leaf of this block and, therefore, the root of another block.
Both $R^{+}(a^{*})$ and $R^{+}(a^{\prime})\cap L_{a^{*}}$ are subsets of
$L_{a^{*}}$, so $R^{+}(a^{\prime})\subsetneq L_{a^{*}}$. As a conclusion,
$R^{+}(a^{\prime})\cup\left\\{E\left[a^{\prime}\right]\right\\}\subseteq
L_{a^{*}}$ is a POF, therefore $X^{\prime}\cup R^{+}(a^{\prime})$ is a POF and
$(a^{\prime},X^{\prime})$ is thus a constraint pair.

We show that $I(a^{\prime},X^{\prime})=(a,X)$. We refer to Case B*: the
$\Theta$-class $E\left[a^{\prime}\right]$ belongs to $X^{\prime}$, so function
$I$ returns
$(a^{-},X^{\prime}\backslash\left\\{E\left[a^{\prime}\right]\right\\})=(a,X)$.

$\mathcal{B}_{a^{\prime}}$$a_{0}$$I$$(a_{0},Y)$$(a,X)=I^{k}(a_{0},Y)$$(a^{\prime},X^{\prime})=I^{k+1}(a_{0},Y)$$a^{*}$$a$$a^{\prime}$

Figure 10: Nodes $a$, $a^{\prime}$, and $a^{*}$ in $T$ when $a^{\prime}$ is
not the root of a block in Scenario 1. Blue arrows indicate the successive
appliances of the itinerary function on $(a_{0},Y)$.

  * •

Scenario 2: edge $(a^{\prime},a)$ in $T$ is indexed by
$-E\left[a^{\prime}\right]$ and $X\cup E\left[a^{\prime}\right]$ is not a POF.

Let $X^{\prime}=X$. As $(a,X)\in\mathcal{C}$ and $R(a^{\prime})\subsetneq
R(a)$, we have $X\cap R(a^{\prime})=\emptyset$. Moreover,
$R^{+}(a^{\prime})=R^{+}(a)$, so $X\cap R^{+}(a^{\prime})$ is a POF. In brief,
$(a^{\prime},X^{\prime})=(a^{\prime},X)\in\mathcal{C}$.

We prove that $I(a^{\prime},X^{\prime})=(a,X)$. In this scenario,
$X\cup\left\\{E\left[a^{\prime}\right]\right\\}$ is not a POF. Furthermore,
$X\cap R(a)=\emptyset$ because $(a,X)\in\mathcal{C}$, so
$E\left[a^{\prime}\right]\notin X$. We refer to Case D* and
$I(a^{\prime},X^{\prime})=(a^{-},X^{\prime})=(a,X)$.

  * •

Scenario 3: edge $(a^{\prime},a)$ in $T$ is indexed by
$+E\left[a^{\prime}\right]$.

Let $X^{\prime}=X$. As $(a,X)\in\mathcal{C}$ and $R(a^{\prime})\subsetneq
R(a)$, we have $X\cap R(a^{\prime})=\emptyset$ as in Scenario 2. Moreover,
$R^{+}(a^{\prime})\subsetneq R^{+}(a)$: only $E\left[a^{\prime}\right]$ is in
$R^{+}(a)$ and not in $R^{+}(a^{\prime})$. As $X\cup R^{+}(a)$ is a POF, its
subset $X\cup R^{+}(a^{\prime})$ is too. In brief,
$(a^{\prime},X^{\prime})=(a^{\prime},X)\in\mathcal{C}$.

We show that $I(a^{\prime},X^{\prime})=(a,X)$. Class
$E\left[a^{\prime}\right]$ is not in $X^{\prime}=X$ because $X\cap
R(a)=\emptyset$. Set $X\cup\left\\{E\left[a^{\prime}\right]\right\\}$ is a
subset of the POF $X\cup R^{+}(a)$ because $E\left[a^{\prime}\right]\in
R^{+}(a)$, so $X\cup\left\\{E\left[a^{\prime}\right]\right\\}$ is a POF. We
refer to Case C*: $I(a^{\prime},X^{\prime})=(a^{+},X^{\prime})=(a,X)$.

In summary, there is a constraint pair $(a^{\prime},X^{\prime})$ such that
$a^{\prime}$ is the parent of $a$, $X\subseteq X^{\prime}$, and
$I(a^{\prime},X^{\prime})=(a,X)$. The induction hypothesis terminates the
proof of our claim: as $(a^{\prime},X^{\prime})$ is in some itinerary $f(Y)$
with $X^{\prime}\subseteq Y$, and $I(a^{\prime},X^{\prime})=(a,X)$, then
$(a,X)$ also belongs to $f(Y)$. As the size of each $f(Y)$, $Y\in\mathcal{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
$\left|h(a,X)\right|\leq d$ for any $(a,X)\in V(H)$. For any pair $(a,X)\in
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}n)$ and is thus the total running time of our algorithm.

##  4 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.1 with the proposal of a linear-time FPT algorithm,
parameterized by the dimension $d$, running in $2^{O(d)}n$. It is mainly based
on a paper of the literature [15] which provides a slightly super-exponential
time algorithm - running in $2^{O(d\log d)}n$ \- for the same problem.
Replacing one step of this procedure by the partitioning conceived in Section
3.2 allows us to decrease the exponential dependence on $d$. Thanks to this
outcome, in Section 4.2, we are able to design a first subquadratic-time
algorithm for all median graphs running in $\tilde{O}(n^{\frac{5}{3}})$.

###  4.1 Linear FPT algorithm for constant-dimension median graphs

We remind 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 ([15]).

There is a combinatorial algorithm computing all eccentricities in a median
graph $G$ with running time $\tilde{O}(2^{d(\log d+1)}n)$.

Some parts of this subsection are redundant with [15], however we keep this
subsection self-contained. The new outcomes presented are Theorems 8 and 10.
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 $\varphi$, opposite labels op and anti-ladder labels
$\psi$. The order in which they are given correspond to their respective
dependence: op-labelings are functions of labels $\varphi$ and
$\psi$-labelings are functions of both labels $\varphi$ 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.

####  4.1.1 Definition of the POF-parallelism

We present a notion related to orthogonality which will be used in the
remainder.

######  Definition 11 ($L$-parallelism).

Given a POF $L$, we say that a POF $L^{+}$ is $L$-_parallel_ if, for any
$E_{j}\in L^{+}$, $L\cup\left\\{E_{j}\right\\}$ is not a POF.

Presented differently, a $L$-parallel POF is such that any of its
$\Theta$-classes is parallel to at least one $\Theta$-class of $L$. When
$L^{+}$ is a $L$-parallel POF, we have $L\cap L^{+}=\emptyset$, otherwise
$L\cup\left\\{E_{j}\right\\}=L$ for some $E_{j}\in L^{+}$. We extend
Definition 11 by adding the notion of adjacency.

######  Definition 12.

Given a pair $L,L^{+}$ of POFs, we say that $L^{+}$ is $L$-parallel-adjacent
if:

  * •

$L^{+}$ is $L$-parallel,

  * •

there exists a vertex $u$ such that $L$ is ingoing into $u$ and $L^{+}$ is
outgoing from $u$.

Given a POF $L$, we denote by $\parallel_{\mbox{\scriptsize{P}}}(L)$ the set
of POFs $L^{+}$ which are $L$-parallel-adjacent. As an example, in Figure 11,
$\left\\{E_{4},E_{5}\right\\}\in\parallel_{\mbox{\scriptsize{P}}}(\left\\{E_{2},E_{3}\right\\})$
but
$\left\\{E_{1}\right\\}\notin\parallel_{\mbox{\scriptsize{P}}}(\left\\{E_{2},E_{3}\right\\})$.
Similarly, for a pair signature/anti-basis $(L,u)$, defining an hypercube:

######  Definition 13.

We say POF $L^{+}$ is $(L,u)$-parallel if $L^{+}$ is both $L$-parallel and
outgoing from $u$.

We denote by $\parallel_{\mbox{\scriptsize{P}}}(L,u)$ the set of
$(L,u)$-parallel POFs. Observe now that, in this hypercube viewpoint, the
adjacency between the two POFs $L$ and $L^{+}$ is fixed by the existence of
the anti-basis $u$ of $(L,u)$.

Our future algorithms will be strongly based on the enumeration of sets
$\parallel_{\mbox{\scriptsize{P}}}(L)$, for all POFs $L$, but also of sets
$\parallel_{\mbox{\scriptsize{P}}}(L,u)$ for all pairs signature/anti-basis.
As a first version, our algorithm uses only the enumeration of all sets
$\parallel_{\mbox{\scriptsize{P}}}(L,u)$, executed in a naive way. Indeed, we
know from Lemma 10 that the number of $\Theta$-classes ingoing into $u$ is $d$
and that they are all pairwise orthogonal. Furthermore, all pairs $(u,L^{+})$
such that $L^{+}$ is outgoing from $u$ can be enumerated in
$\tilde{O}(2^{d}n)$. All in all, one can enumerate all sets
$\parallel_{\mbox{\scriptsize{P}}}(L,u)$ in time $\tilde{O}(2^{2d}n)$.

######  Theorem 6.

There is an algorithm, running in time $\tilde{O}(2^{2d}n)$, which returns all
sets $\parallel_{\mbox{\scriptsize{P}}}(L,u)$.

###### Proof.

Enumerate all hypercubes of $G$ in $\tilde{O}(2^{d}n)$ (Lemma 12). We obtain
all possible pairs $(u,L^{+})$, where POF $L^{+}$ is outgoing from $u$. Then,
among the $d$ $\Theta$-classes ingoing into $u$, try all collections of sets
(at most $2^{d}$). These collections are POFs, since the $\Theta$-classes
ingoing into $u$ are pairwise orthogonal (Lemma 10). For each of these POFs
$L$, verify whether $L^{+}$ is $L$-parallel. As
$\left|L\right|,\left|L^{+}\right|\leq d$, this is done in logarithmic time
$O(d^{2})$. The total running time is thus $\tilde{O}(2^{2d}n)$. ∎

In Section 5, we propose a better algorithm to enumerate these “parallel-
adjacency” lists. For the moment, in Section 4, we will use the naive version
proposed in Theorem 6.

####  4.1.2 Ladder labels

Some preliminary work has to be done before giving the definition of labels
$\varphi$. We introduce the notion of ladder set. It is defined only for pairs
of vertices $u,v$ satisfying the condition $u\in 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 14 (Ladder set $L_{u,v}$).

Let $u,v\in V$ such that $u\in I(v_{0},v)$. The ladder set $L_{u,v}$ is the
subset of $\sigma_{u,v}$ which contains the $\Theta$-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\in I(v_{0},v)$ and $u\in I(v_{0},x)$. It gives the composition of
ladder sets $L_{u,v}$ and $L_{u,x}$.

$E_{1}$$E_{2}$$E_{3}$$E_{4}$$E_{5}$$v_{0}$$u$$v$$x$

Figure 11: Examples of ladder sets: $L_{u,v}=\left\\{E_{2},E_{3}\right\\}$,
$L_{u,x}=\left\\{E_{1},E_{2},E_{3}\right\\}$.

A key characterization on ladder sets states that their $\Theta$-classes are
pairwise orthogonal. In brief, every set $L_{u,v}$ is a POF. Let us remind
that the adjacency of all $\Theta$-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 $\Theta$-class of $L$ leave $u$ -, then $u$ is the basis of the hypercube.
As the $\Theta$-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,\cdot})$.

######  Lemma 17 ([15]).

Every ladder set $L_{u,v}$ is a POF. For any ordering $\tau$ of the
$\Theta$-classes in $L_{u,v}$, there is a shortest $(u,v)$-path such that, for
any $1\leq i\leq\left|L_{u,v}\right|$, the $i^{\mbox{\scriptsize{th}}}$ first
edge of the path belongs to the $i^{\mbox{\scriptsize{th}}}$ $\Theta$-class of
$L_{u,v}$ in ordering $\tau$.

The necessary background to introduce labels $\varphi$ is now known.

######  Definition 15 (Labels $\varphi$ [15]).

Given a vertex $u$ and a POF $L$ outgoing from $u$, let $\varphi(u,L)$ be the
maximum distance $d(u,v)$ such that $u\in I(v_{0},v)$ and $L_{u,v}=L$.

Intuitively, integer $\varphi(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 $\varphi$ on a median graph $G$ does not exceed $O(2^{d}n)$,
according to Lemma 11.

A combinatorial algorithm running in $\tilde{O}(2^{2d}n)$ which computes all
labels $\varphi(u,L)$ was identified in [15]: we provide an overview of it.
There is a crucial relationship between a label $\varphi(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 $\varphi$ [15]).

Let $u\in 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\neq
u^{+}$ verifies $u\in I(v_{0},v)$ and $L_{u,v}=L$ if and only if (i) $u^{+}\in
I(v_{0},v)$ and (ii) ladder set $L_{u^{+},v}$ is $(L,u^{+})$-parallel.

A consequence of the previous lemma is that we can distinguish two cases for
the computation of $\varphi(u,L)$. In the first case,
$\varphi(u,L)=\left|L\right|$: it occurs when the farthest-to-$u$ vertex with
ladder set $L$ is $u^{+}$ (base case). Indeed, $u^{+}$ is a candidate as
$\sigma_{u,u^{+}}=L$: shortest $(u,u^{+})$-paths pass through hypercube $Q$.
This situation happens when either no $\Theta$-class is outgoing from $u^{+}$
or when all $\Theta$-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, $\varphi(u,L)$ is a function of labels
$\varphi(u^{+},\cdot)$.

$\begin{split}\varphi(u,L)&=\max\limits_{\begin{subarray}{c}L^{+}~{}\mbox{\scriptsize{POF
outgoing from}}~{}u^{+}\\\ \forall E_{j}\in
L^{+},~{}L\cup\left\\{E_{j}\right\\}~{}\mbox{\scriptsize{not
POF}}\end{subarray}}(\left|L\right|+\varphi(u^{+},L^{+})).\\\
&=\max\limits_{\begin{subarray}{c}(L,u^{+})\mbox{\scriptsize{-parallel}}\\\
\mbox{\scriptsize{POFs}}~{}L^{+}\end{subarray}}(\left|L\right|+\varphi(u^{+},L^{+})).\end{split}$
(4)

If there exists such a POF $L^{+}$, then the label $\varphi(u,L)$ is given by
Equation (4). Otherwise, it is given by the first case. Observe that the POFs
$L^{+}$ that are taken into account in Equation (4) are exactly the POFs such
that $L^{+}$ is $(L,u^{+})$-parallel. Briefly, the algorithm consists in
listing all triplets $(L,u^{+},L^{+})$ such that $L^{+}$ is
$(L,u^{+})$-parallel. (Definition 13). Vertex $u$ is deduced, as it is the
basis of the hypercube with signature $L$ and anti-basis $u^{+}$. We update
$\varphi(u,L)$ if $\left|L\right|+\varphi(u^{+},L^{+})$ is greater than the
current value. The total number of triplets $(L,u^{+},L^{+})$ is upper-bounded
by $2^{2d}n$ and can be enumerated in $\tilde{O}(2^{2d}n)$ (Theorem 6). For
this reason, the computation of $\varphi$-labelings takes
$\tilde{O}(2^{2d}n)$.

######  Theorem 7 (Computation of labels $\varphi$ [15]).

There is a combinatorial algorithm which determines all labels $\varphi(u,L)$
in $\tilde{O}(2^{2d}n)$. It also stores, for each pair $(u,L)$, a vertex $v$
satisfying $L_{u,v}=L$ and $d(u,v)=\varphi(u,L)$, denoted by $\mu(u,L)$.

####  4.1.3 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 $\mbox{{op}}_{u}(L)$ denote a POF with maximum label
$\varphi$ which is disjoint from $L$. As for $\varphi$, the total size of op-
labelings is $O(2^{d}n)$.

######  Definition 16 (Labels op [15]).

Let $u\in V$ and $L$ be a POF outgoing from $u$. Let $\mbox{{op}}_{u}(L)$ be
one of the POF $L^{\prime}$ outgoing from $u$, disjoint from $L$, which
maximizes value $\varphi(u,L^{\prime})$.

On simplex graphs, the opposite function provides in fact the op-labelings of
vertex $v_{0}$: $\mbox{{op}}(X)=\mbox{{op}}_{v_{0}}(X)$. As all vertices
belong to hypercubes with basis $v_{0}$, the ladder set $L_{v_{0},v}$ for any
vertex $v\in V$ is exactly the set $\mathcal{E}^{-}(v)$ of $\Theta$-classes
incoming into $v$. So, value $\varphi(v_{0},X)$ is the distance $d(v_{0},v)$
between $v_{0}$ and the only vertex $v$ with ladder set $L_{v_{0},v}=X$.

On general median graphs, the opposite label $\mbox{{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
[15]).

Let $L,L^{\prime}$ be two POFs outgoing from a vertex $u$. Let $s$ (resp. $t$)
be a vertex such that $u\in I(v_{0},s)$ (resp. $u\in I(v_{0},t)$) and
$L_{u,s}=L$ (resp. $L_{u,t}=L^{\prime}$). Then, $u\in I(s,t)$ if and only if
$L\cap L^{\prime}=\emptyset$. Therefore, given a single vertex $s$ such that
$u\in I(v_{0},s)$ and $L_{u,s}=L$, the maximum distance $d(s,v)$ we can have
with median $m(s,v,v_{0})=u$ is exactly
$d(u,s)+\varphi(u,\mbox{{op}}_{u}(L))$.

Going further, given a vertex $u\in V$, the maximum distance $d(s,t)$ such
that $u=m(s,t,v_{0})$ is the maximum value
$\varphi(u,L)+\varphi(u,\mbox{{op}}_{u}(L))$, where $L$ is POF outgoing from
$u$.

An algorithm was initially proposed to compute all labels $\mbox{{op}}_{u}(L)$
consisting in a brute force bounded tree search [15]. Its execution time was
$\tilde{O}(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\in V$, let
$G_{u}=G\left[V_{u}\right]$ be the star graph of $u$, using a definition from
[22]. 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. [22]
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 8 (Computation of labels op).

There is a combinatorial algorithm which determines all labels
$\mbox{{op}}_{u}(L)$ in $\tilde{O}(2^{d}n)$.

###### Proof.

Let $u\in V$: we denote by $N_{u}$ 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
$G_{u}$ is median and all its maximal hypercubes contain a common vertex $u$.
From Theorem 2, $G_{u}$ is a simplex graph.

$v_{0}$$u$

(a) A $v_{0}$-oriented median graph $G$ and a vertex $u\in V$

$u$

(b) Star graph $G_{u}$

Figure 12: Example of star graph $G_{u}$

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 $G_{u}$ (ii) the vertices of
$G_{u}$ and (iii) the POFs $L$ of $G$ outgoing from $u$. Hence,
$\left|V_{u}\right|=N_{u}$.

We associate with any POF $L$ of $G_{u}$ the weight
$\omega_{u}(L)=\varphi(u,L)$. We solve WOPP on graph $G_{u}$ with weight
function $\omega_{u}$, using the algorithm evoked in Theorem 3. The opposite
computed with that configuration correspond exactly to the labels
$\mbox{{op}}_{u}(L)$: a POF $L^{\prime}$ disjoint from $L$ and maximizing
$\varphi(u,L^{\prime})$ among all POFs outgoing from $u$. The running time of
the algorithm is
$O((d^{3}+\log\left|V_{u}\right|)\left|V_{u}\right|)=O((d^{3}+\log n)N_{u})$.
Doing it for every vertex $u$ of $G$, we obtain all opposite labels of $G$ in
$O(d^{3}+\log n)2^{d}n)$ as $\sum_{u\in V}N_{u}=2^{d}n$ (Lemma 11). ∎

####  4.1.4 Anti-ladder labels

We terminate with anti-ladder labels $\psi$ which play the converse role of
ladder labels $\varphi$. While $\varphi(u,L)$ is defined for POFs $L$ outgoing
from $u$, labels $\psi(u,R)$ are defined for POFs $R$ incoming into $u$, i.e.
every $\Theta$-class of the POF $R$ 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 $\psi$-labelings is at most $O(2^{d}n)$ too.

The notion of milestone intervenes in the definition of labels $\psi$. We
consider two vertices $u,v$ such that $u\in I(v_{0},v)$. Milestones are
defined recursively.

######  Definition 17 (Milestones $\Pi(u,v)$).

Let $L_{u,v}$ be the ladder set of $u,v$ and $u^{+}$ be the anti-basis of the
hypercube with basis $u$ and signature $L_{u,v}$. If $u^{+}=v$, then pair
$u,v$ admits two milestones: $\Pi(u,v)=\left\\{u,v\right\\}$. Otherwise, the
set $\Pi(u,v)$ is the union of $\Pi(u^{+},v)$ with vertex $u$:
$\Pi(u,v)=\left\\{u\right\\}\cup\Pi(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 $\Pi(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$: $\Pi(u,v)\subseteq I(u,v)$.

######  Definition 18 (Penultimate milestone $\overline{\pi}(u,v)$).

We say that the milestone in $\Pi(u,v)$ different from $v$ but the closest to
it is called the penultimate milestone. We denote it by $\overline{\pi}(u,v)$.
Furthermore, we denote by $\overline{L}_{u,v}$ the _anti-ladder set_ of $u,v$,
i.e. the $\Theta$-classes of the hypercube with basis $\overline{\pi}(u,v)$
and anti-basis $v$.

$L_{u,v}$$L_{u^{+},v}$$L_{u^{++},v}$$v_{0}$$u$$v$$u^{+}$$u^{++}$

Figure 13: A pair $u,v$ with $u\in I(v_{0},v)$ and its milestones $\Pi(u,v)$
in red.

Figure 13 shows the milestones $\Pi(u,v)=\left\\{u,u^{+},u^{++},v\right\\}$.
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 $\overline{\pi}(u,v)=u^{++}$ and
$\overline{L}_{u,v}=L_{u^{++},v}$ is drawn 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 $\psi(u,R)$ intuitively
represents the maximum distance of a shortest path arriving to vertex $u$ from
“direction” $R$.

######  Definition 19 (Labels $\psi$ [15]).

The label $\psi(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})\neq u$,

  * •

the anti-ladder set of $m,u$ is $R$: $\overline{L}_{m,u}=R$.

Equivalently, vertex $u^{-}$ is the penultimate milestone of pair $m,u$:
$u^{-}=\overline{\pi}(m,u)$.

As for the computation of labels $\varphi$, there is an induction process to
determine all $\psi(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}\in
I(u,v)$ consists in considering the opposite $\mbox{{op}}_{v_{0}}(R)$ of $R$
which is outgoing from $v_{0}$. Hence,
$\psi(u,R)=\left|R\right|+\varphi(v_{0},\mbox{{op}}_{v_{0}}(R))$.

For the induction step, we distinguish two cases. In the first one, assume
that $m(u,v,v_{0})=u^{-}$ \- equivalently,
$\Pi(m,u)=\Pi(u^{-},u)=\left\\{u^{-},u\right\\}$. A shortest $(u,v)$-path is
the concatenation of the shortest $(u,u^{-})$-path of length $\left|R\right|$
with a shortest $(u^{-},v)$-path, and $u^{-}\in I(v_{0},v)$. The largest
distance $d(u,v)$ we can have, as for the base case, is
$\psi(u,R)=\left|R\right|+\varphi(u^{-},\mbox{{op}}_{u^{-}}(R))$.

In the second case, $m\neq u^{-}$, an inductive formula allows us to obtain
$\psi(u,R)$. A consequence of Lemma 18 is that, for two consecutive milestones
in $\Pi(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 $\psi$ [15]).

Let $u,v\in V$ and $u\in 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:

  1. (i)

vertex $v$ is the penultimate milestone of $(u,w)$: $\overline{\pi}(u,w)=v$,

  2. (ii)

the milestones of $(u,w)$ are the milestones of $(u,v)$ with $w$:
$\Pi(u,w)=\Pi(u,v)\cup\left\\{w\right\\}$,

  3. (iii)

the POF $L$ is $\overline{L}_{u,v}$-parallel.

Set $\Pi(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^{-}\cup\left\\{E_{j}\right\\}$ is not a POF, for each
$E_{j}\in R$. For this reason, value $\psi(u,R)$ can be expressed as:

$\begin{split}\psi(u,R)&=\max\limits_{\begin{subarray}{c}R^{-}~{}\mbox{\scriptsize{POF
incoming to}}~{}u^{-}\\\ \forall E_{j}\in
R,R^{-}\cup\left\\{E_{j}\right\\}~{}\mbox{\scriptsize{not
POF}}\end{subarray}}(\left|R\right|+\psi(u^{-},R^{-}))\\\
&=\max\limits_{\begin{subarray}{c}(R^{-},u^{-})~{}\mbox{\scriptsize{s.t.}}\\\
R~{}\mbox{\scriptsize{is}}~{}(R^{-},u^{-})\mbox{\scriptsize{-parallel}}\end{subarray}}(\left|R\right|+\psi(u^{-},R^{-})).\end{split}$
(5)

Our algorithm consists in taking the maximum value between the two cases. The
number of triplets $(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
$\varphi$-labelings (Theorem 6).

######  Theorem 9 (Computation of labels $\psi$ [15]).

There is a combinatorial algorithm which determines all labels $\psi(u,R)$ in
$\tilde{O}(2^{2d}n)$.

####  4.1.5 Better time complexity for all eccentricities

The computation of all labels $\varphi(u,L)$, $\mbox{{op}}_{u}(L)$ and
$\psi(u,R)$ gives an algorithm which determines all eccentricities. Indeed,
each eccentricity $\mbox{{ecc}}(u)$ is a function of certain labels $\varphi$
and $\psi$. Let $v$ be a vertex in $G$ such that $\mbox{{ecc}}(u)=d(u,v)$. If
$m=m(u,v,v_{0})=u$, then $u\in I(v_{0},v)$ and value $d(u,v)$ is given by a
label $\varphi(u,L)$. Otherwise, if $m\neq u$, let $u^{-}$ be the penultimate
milestone in $\Pi(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
$\psi(u,R)$. Conversely, each $\varphi(u,L)$ and $\psi(u,R)$ is the distance
between $u$ and another vertex by definition. Therefore, we have:

$\mbox{{ecc}}(u)=\mbox{max}\left\\{\max\limits_{\begin{subarray}{c}L~{}\mbox{\scriptsize{POF}}\\\
\mbox{\scriptsize{outgoing
from}}~{}u\end{subarray}}\varphi(u,L),\max\limits_{\begin{subarray}{c}R~{}\mbox{\scriptsize{POF}}\\\
\mbox{\scriptsize{incoming to}}~{}u\end{subarray}}\psi(u,R)\right\\}$ (6)

In other words, the eccentricity of $u$ is the maximum label $\varphi$ or
$\psi$ 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 10 (All eccentricities in $\tilde{O}(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 $\tilde{O}(2^{2d}n)$.

###### Proof.

We simply determine the labels $\varphi$, op and $\psi$ with the algorithms
mentioned in Theorem 7, 8, and 9. Thanks to the time improvement obtained for
the computation of opposite labels, the overall running time to compute the
labels is only $\tilde{O}(2^{2d}n)$. Then, for each vertex $u$, Equation (6)
guides us to obtain its eccentricity. We take the maximum over all labels
$\varphi(u,L)$ \- they are at most $N_{u}$ \- and all labels $\psi(u,R)$ \-
they are at most $2^{d}$. As $\sum_{u}N_{u}\leq 2^{d}n$, the execution time of
this operation on all vertices is $\tilde{O}(2^{d}n)$. Therefore, it does not
overpass the time complexity needed to determine the labels. ∎

###  4.2 Tackling the general case

Our new FPT algorithm for computing the list of eccentricities in a median
graph has a runtime in $2^{{\cal O}(d)}n$, with $d$ being the dimension
(Theorem 10). This runtime stays subquadratic in $n$ as long as
$d<\alpha\cdot\log{n}$, for some constant $\alpha<1$. In what follows, we
present a simple partitioning scheme for median graphs into convex subgraphs
of dimension at most $\alpha\cdot\log{n}$, for an arbitrary value of
$\alpha\leq 1$. By doing so, we obtain (in combination with Theorem 10) 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\leq i\leq q$, let $v\in
V(H_{i}^{\prime})$ be arbitrary, and let $v^{*}$ be its gate in $\partial
H_{i}^{\prime\prime}$. Then,
$\mbox{{ecc}}(v)=\max\\{\mbox{{ecc}}_{H_{i}^{\prime}}(v),d(v,v^{*})+\mbox{{ecc}}_{H_{i}^{\prime\prime}}(v^{*})\\}$.

###### Proof.

We have $\mbox{{ecc}}(v)=\mbox{{ecc}}_{G}(v)=\max\\{d(u,v)\mid u\in
V(H_{i}^{\prime})\\}\cup\\{d(w,v)\mid w\in V(H_{i}^{\prime\prime})\\}$. Since
$H_{i}^{\prime}$ is convex, we have $\max\\{d(u,v)\mid u\in
V(H_{i}^{\prime})\\}=\mbox{{ecc}}_{H_{i}^{\prime}}(v)$. In the same way, since
$H_{i}^{\prime\prime}$ is gated (and so, convex), we have $\max\\{d(w,v)\mid
w\in V(H_{i}^{\prime\prime})\\}=d(v,v^{*})+\max\\{d(v^{*},w)\mid w\in
V(H_{i}^{\prime\prime})\\}=d(v,v^{*})+\mbox{{ecc}}_{H_{i}^{\prime\prime}}(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 $\Theta$-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 $\Theta$-class of $H$ is contained in a $\Theta$-class of $G$.

###### Proof.

Every square of $H$ is also a square of $G$. In particular, two edges of $H$
are in relation $\Theta_{0}$ if and only if, as edges of $G$, they are also in
relation $\Theta_{0}$. Since the $\Theta$-classes of $H$ (resp., of $G$) are
the transitive closure of its relation $\Theta_{0}$, it follows that every
$\Theta$-class of $H$ is contained in a $\Theta$-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},\ldots,E_{q}$ denote
the $\Theta$-classes of $G$. If $H$ is an isometric subgraph of $G$ then, the
$\Theta$-classes of $H$ are exactly the nonempty subsets among $E_{i}\cap
E(H)$, for $1\leq i\leq q$.

###### Proof.

It is known [42] that two edges $uv,xy$ of $G$ are in the same $\Theta$-class
if and only if $d_{G}(u,x)+d_{G}(v,y)\neq d_{G}(u,y)+d_{G}(v,x)$. In
particular, since $H$ is isometric in $G$, two edges of $H$ are in the same
$\Theta$-class of $H$ if and only if they are in the same $\Theta$-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 $\Theta$-classes.

######  Lemma 24.

Let $G$ be a median graph, and let $D:=\max\\{|E_{i}|\mid 1\leq i\leq q\\}$ be
the maximum cardinality of a $\Theta$-class of $G$. Then,
$d=\dim(G)\leq\lfloor\log{D}\rfloor+1$.

###### Proof.

Any induced $d$-dimensional hypercube of $G$ contains exactly $2^{d-1}$ edges
of its $\Theta$-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 $\tilde{O}(c^{d}\cdot n)$ time, then
in $\tilde{O}(n^{2-\frac{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 $\Theta$-classes
$E_{1},E_{2},\ldots,E_{q}$, 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},\ldots,E_{p}$ to be the subset of all $\Theta$-classes
of cardinality $\geq D$, for some $p\leq q$. Note that we have $p\leq
m/D=\tilde{O}(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\setminus(E_{1}\cup
E_{2}\cup\ldots\cup E_{p})$. More formally, we construct a rooted binary
tree111This tree $T$ is independent to the one built in Section 3.2 $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\ldots 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\setminus\left(E_{1}\cup
E_{2}\cup\ldots\cup E_{i}\right)$. An example of $T$ is shown in Figure 14
with $D=3$ and two $\Theta$-classes reaching this cardinality bound.

For that, we proceed as follows. We consider all leaves of $T$ whose label $H$
satisfies $E(H)\cap E_{i}\neq\emptyset$. By Lemma 23, $E(H)\cap E_{i}$ is a
$\Theta$-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\setminus(E_{1}\cup E_{2}\cup\ldots\cup 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)=\tilde{O}(n^{2}/D)$.

$E_{1}$$E_{2}$$H_{1}^{\prime\prime}$$H_{1}^{\prime}$

Figure 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
$\mbox{dim}(H)\leq\lfloor\log{D}\rfloor+1$. Indeed, by Lemma 22, every
$\Theta$-class of $H$ is contained in a $\Theta$-class of $G$. Since we
removed all $\Theta$-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
$\tilde{O}(c^{\lfloor\log{D}\rfloor+1}|V(H)|)=\tilde{O}(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
$\tilde{O}(D^{\log{c}}n)$.

  * •

From now on, let us assume $H$ labels an internal node of $T$ (inductive
case). Let $H_{i}^{\prime},H_{i}^{\prime\prime}$ be its children nodes,
obtained from the removal of $E(H)\cap E_{i}$ for some $1\leq i\leq p$. – For
convenience, we will say later in the proof that $H$ is an $i$-node. – Recall
that $E(H)\cap E_{i}$ is a $\Theta$-class of $H$. In particular,
$H_{i}^{\prime},H_{i}^{\prime\prime}$ are gated subgraphs. By Lemma 21, we can
compute in ${O}(|V(H_{i}^{\prime})|)$ time the eccentricities in $H$ of all
vertices in $H_{i}^{\prime}$ if we are given as input: the list of
eccentricities in $H_{i}^{\prime}$, the list of eccentricities in
$H_{i}^{\prime\prime}$, and for every $v\in V(H_{i}^{\prime})$ its gate
$v^{*}\in\partial H_{i}^{\prime\prime}$ and the distance $d(v,v^{*})$. The
respective lists of eccentricities for $H_{i}^{\prime}$ and
$H_{i}^{\prime\prime}$ were pre-computed by dynamic programming on $T$.
Furthermore, we can compute the gate $v^{*}$ and $d(v,v^{*})$ for every vertex
$v\in V(H_{i}^{\prime})$, in total $\tilde{O}(|V(H)|)$ time, by using a
modified BFS rooted at $H_{i}^{\prime\prime}$ (we refer to [22, Lemma 17] for
a detailed description of this standard procedure). Overall (by proceeding the
same way for $H_{i}^{\prime\prime}$ as for $H_{i}^{\prime}$) we can compute
the list of eccentricities for $H$ in $\tilde{O}(|V(H)|)$ time. This is in
total $\tilde{O}(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
$\tilde{O}(pn)=\tilde{O}(n^{2}/D)$ time for all the internal nodes.

The total runtime for our algorithm is in $\tilde{O}(n^{2}/D+D^{\log{c}}n)$,
that is optimized for $D=n^{\frac{1}{\log{c}+1}}$. ∎

######  Theorem 11.

There is an $\tilde{O}(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 10 with Lemma 25
(applied for $c=4$). ∎

Observe that the design of a linear FPT algorithm for eccentricities in
$\tilde{O}(c^{d}n)$ with $c<4$ would imply a lower subquadratic constant for
this problem. Such an algorithm is proposed in Section 5.3.

##  5 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 $\varphi$, op, and $\psi$ are already
known. A consequence is the existence of an exact algorithm for the reach
centrality in $\tilde{O}(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 $\varphi$, op and
$\psi$ based on this structure. This yields a second subquadratic-time
algorithm which determines all eccentricities with a better running time.

Finally, we introduce a new relationship between POFs: the minimal
parallelism. It allows us to design a linear FPT algorithm for eccentricities
on median graphs in time $\tilde{O}(3.5394^{d}n)$, which outperforms the
running time obtained in Section 4.1. Furthemore, we deduce from it a third
subquadratic-time algorithm which provides us with the best running time so
far: $\tilde{O}(n^{1.6408})$.

###  5.1 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 $\mbox{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 [26]. The relationship between reach
centrality and the well-known metric parameters has been studied: Abboud et
al. [1] proved that determining the diameter and the reach centrality are
equivalent under subcubic reductions. The formal definition of $\mbox{RC}(u)$
follows.

$\mbox{RC}(u)=\max_{u\in I(s,t)}\min\left\\{d(s,u),d(u,t)\right\\}$ (7)

In Theorem 10, we showed that all eccentricities of a median graph are
functions of the labelings $\varphi$, op, and $\psi$. 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\in V$, there are two vertices $s,t$ such that
$d(u,s)=\varphi(u,L)$, $d(u,t)=\psi(u,R)$ and $u\in I(s,t)$.

######  Theorem 12.

Let $u\in 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 $\overline{L}_{m,u}=R$.

  * •

The distance $d(u,s)$ and $d(u,t)$ are given by the labels:
$d(u,s)=\varphi(u,L)$ and $d(u,t)=\psi(u,R)$.

  * •

Vertex $u$ belongs to the interval $I(s,t)$.

###### Proof.

Let $s$ be a vertex such that $u\in I(v_{0},s)$, $L_{u,s}=L$ and
$d(u,s)=\varphi(u,L)$. Let $t$ be a vertex such that $\overline{L}_{m,u}=R$
for $m=m(u,t,v_{0})$, and $d(u,t)=\psi(u,R)$. By definition of labels
$\varphi$ and $\psi$, such vertices exist. At this moment, the three first
bullets are verified. To show the fourth one, $u\in I(s,t)$, we prove that the
signatures $\sigma_{u,s}$ and $\sigma_{u,t}$ are disjoint. Assume there is a
$\Theta$-class $E_{i}\in\sigma_{u,s}\cap\sigma_{u,t}$.

Claim 1: $u\in H_{i}^{\prime}$. As $E_{i}\in\sigma_{u,s}$, any shortest
$(u,s)$-path contains an edge of $E_{i}$. Let $(u^{\prime},v^{\prime})$ be one
of these edges of $E_{i}$ which is as close as possible from $u$. Vertex
$u^{\prime}$ \- the endpoint of this edge closer to $u$ \- belongs to
$\partial H_{i}^{\prime}$. Moreover, there is a shortest $(u,s)$-path
$P_{u,s}$ passing through $(u^{\prime},v^{\prime})$ because $v^{\prime}$ is
the gate of $u$ in $H_{i}^{\prime\prime}$. As $u\in I(v_{0},s)$ and
$u^{\prime}\in I(u,s)$, then $u\in I(v_{0},u^{\prime})$. We know that both
$v_{0}$ and $u^{\prime}$ belong to $H_{i}^{\prime}$: by convexity of
halfspaces, $u\in H_{i}^{\prime}$.

Claim 2: $u\in H_{i}^{\prime\prime}$. We have $E_{i}\in\sigma_{u,t}$: we prove
that $E_{i}$ is necessarily in $\sigma_{m,u}$ and not in $\sigma_{m,t}$. The
class $E_{i}$ cannot form a POF if we add it to $R$. We already know it if
$E_{i}\in L$. We prove that: if it was the case for a class
$E_{i}\in\sigma_{u,s}\backslash L$, then it would imply the orthogonality of
$R$ and all $\Theta$-classes of $L$, a contradiction. Indeed, let $z$ be the
vertex such that $\mathcal{E}^{-}(z)=R\cup\left\\{E_{i}\right\\}$. We have
$v^{\prime},z\in\partial H_{i}^{\prime\prime}$. As $v^{\prime}$ is the gate of
$u$ in $H_{i}^{\prime\prime}$, there is a shortest $(u,z)$-path passing
through $(u^{\prime},v^{\prime})$. We denote by $\partial
H_{R}^{\prime\prime}$ the intersection of all $\partial H_{j}^{\prime\prime}$
for all $E_{j}\in R$. As $u,z\in\partial H_{R}^{\prime\prime}$, which is
convex, all vertices metrically between $u$ and $z$ belong to $\partial
H_{R}^{\prime\prime}$, in particular $v^{\prime}$. The ladder set of
$u,v^{\prime}$ is the same as $u,s$ because $v^{\prime}$ does not belong to
the hypercube $Q_{u,L}$ of basis $u$ and signature $L$: $L_{u,v^{\prime}}=L$.
In brief, $Q_{u,L}\subsetneq I(u,v^{\prime})$. So, all $\Theta$-classes of $R$
are adjacent to the vertices of $Q_{u,L}$, a contradiction as $R\cup L$ is not
a POF.

We know now that there is a class $E_{j}\in R$ such that $E_{i}$ and $E_{j}$
are parallel. Thus, $H_{i}^{\prime\prime}\subsetneq H_{j}^{\prime\prime}$.
Suppose, by way of contradiction, that $E_{i}\in\sigma_{m,t}$. Vertex $t$ is
in $H_{i}^{\prime\prime}$, so it is also in $H_{j}^{\prime\prime}$. As
$E_{j}\in R\subseteq\sigma_{m,u}$, then $m\in H_{j}^{\prime}$: $m$ and $t$ are
not in the same halfspace of $E_{j}$. In other words, $E_{j}\in\sigma_{m,t}$.
This is a contradiction because $E_{j}$ is both in $\sigma_{m,u}$ and
$\sigma_{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}\in\sigma_{m,u}$ and $u\in H_{i}^{\prime\prime}$.

Both Claims 1 and 2 yield a contradiction: the signature sets $\sigma_{u,s}$
and $\sigma_{u,t}$ are disjoint. Therefore, $u\in I(s,t)$. ∎

We present now an algorithm which determines, for any vertex $u\in V$, a label
$\chi(u)$. The vertices can be considered in any arbitrary order. The
objective is to obtain, at the end of the execution, $\chi(u)=\mbox{RC}(u)$,
for any vertex $u$. To start, we fix all $\chi(u)$ equal to 0. Let
$\xleftarrow{\max}$ be the operator which modify the left-hand side variable
with the maximum between itself and the right-hand side one. Formally, for
$a\in\mathbb{N}$, $\chi(u)\xleftarrow{\max}a$ is equivalent to
$\chi(u)\leftarrow\max\left\\{\chi(u),a\right\\}$. Given a vertex $u\in 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\in
I(v_{0},s)$, the extremity $t$ maximizing $d(u,t)$ such that $u=m(s,t,v_{0})$
is at distance $\varphi(u,\mbox{{op}}(L_{u,s}))$, according to Lemma 19. If
$d(u,s)\leq\varphi(u,L_{u,s})\leq\varphi(u,\mbox{{op}}_{u}(L_{u,s}))$, then
distance $d(u,s)$ has no influence on $\mbox{RC}(u)$ as another candidate -
any vertex at distance $\varphi(u,L_{u,s})$ from $u$ \- overpasses it.
Moreover, if
$d(u,s)\leq\varphi(u,\mbox{{op}}_{u}(L_{u,s}))\leq\varphi(u,L_{u,s})$, then
$d(u,s)$ also cannot be equal to $\mbox{RC}(u)$ because
$\varphi(u,\mbox{{op}}_{u}(L_{u,s}))$ overpasses it and will count, according
to Lemma 19 and the fact that $\varphi(u,L_{u,s})$ is greater than it.
Eventually, if $d(u,s)>\varphi(u,\mbox{{op}}_{u}(L_{u,s}))$, it does not count
as we cannot form a pair $(s,t)$ such that $u\in I(s,t)$ and $d(s,u)\leq
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 $\varphi$-labelings
$\varphi(u,L)$. We modify label $\chi(u)$ according to these observations.

For any POF $L$ outgoing from $u$, if
$\varphi(u,L)<\varphi(u,\mbox{{op}}_{u}(L))$, then modify the label
$\chi(u)\xleftarrow{\max}\varphi(u,L)$, otherwise do nothing.

Step 2: Reach when $u\neq 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=\overline{L}_{m,u}$. According to Lemma 20, $L$ is $R$-parallel. Theorem 12
intervenes: there is a pair of vertices $s^{*},t^{*}$ such that $u\in I(s,t)$,
$L_{u,s^{*}}=L$, $\overline{L}_{m^{*},u}=R$, $d(u,s^{*})=\varphi(u,L)$ and
$d(u,t^{*})=\psi(u,R)$, where $m^{*}=m(s^{*},t^{*},v_{0})$. As
$\varphi(u,L)\geq d(u,s)$ and $\psi(u,R)\geq d(u,t)$, the reach centrality of
$u$ in this step can be written as a function of only
$\varphi,\psi$-labelings. For example, if a POF $L$ admits an anti-ladder set
$R$ such that $\varphi(u,L)<\psi(u,R)$, then it has to be taken into account
for the computation of $\chi(u)$.

For any pair $L,R$ of POFs respectively outgoing from and incoming to $u$ such
that $L$ is $R$-parallel: if $\varphi(u,L)<\psi(u,R)$, we modify the label
$\chi(u)\xleftarrow{\max}\varphi(u,L)$. Otherwise, we set
$\chi(u)\xleftarrow{\max}\psi(u,R)$.

Step 3: Reach when $u\neq m=m(s,t,v_{0})$ and is not a milestone of $m,s$. Let
$u^{\prime}$ be the milestone of $\Pi(m,s)$ and its $u^{\prime\prime}$ its
successor in $\Pi(m,s)$ such that $u$ belongs to the hypercube of basis
$u^{\prime}$, anti-basis $u^{\prime\prime}$ and, hence, signature
$L=L_{u^{\prime},u^{\prime\prime}}=\sigma_{u^{\prime},u^{\prime\prime}}$. We
distinguish two cases.

\- Case 1: $u^{\prime}$ is the median of $s,t,v_{0}$. In this case, the
distance $d(u,s)$ is less than $\varphi(u^{\prime},L)-d(u^{\prime},u)$.
Moreover, the distance $d(u,t)$ is less than
$d(u^{\prime},u)+\varphi(u^{\prime},\mbox{{op}}_{u^{\prime}}(L))$. So, the
reach centrality can be expressed only as a function of labels $\varphi$,
$\psi$, and the distance $d(u^{\prime},u)$.

For any POF $L$ outgoing from some $u^{\prime}\in V$ such that $u$ belongs to
the hypercube of basis $u^{\prime}$ and signature $L$, if
$\varphi(u^{\prime},L)-d(u^{\prime},u)<d(u^{\prime},u)+\varphi(u^{\prime},\mbox{{op}}_{u^{\prime}}(L))$,
then we modify the label
$\chi(u)\xleftarrow{\max}\varphi(u^{\prime},L)-d(u^{\prime},u)$. Otherwise, we
set
$\chi(u)\xleftarrow{\max}d(u^{\prime},u)+\varphi(u^{\prime},\mbox{{op}}_{u^{\prime}}(L))$.

\- Case 2: $u^{\prime}$ is not the median of $s,t,v_{0}$. Let $R$ be the anti-