<figure><img src="image_1.png" /></figure>

HAL
open science

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

Pierre Bergé, Guillaume Ducoffe, Michel Habib

► To cite this version:

Pierre Bergé, Guillaume Ducoffe, Michel Habib. Subquadratic-time Algorithm for the Diameter and all Eccentricities on Median Graphs. Theory of Computing Systems, 2024, 68 (1), pp.144-193. 10.1007/s00224-023-10153-9 . hal-04452245

HAL Id: hal-04452245

https://hal.science/hal-04452245v1

Submitted on 12 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Subquadratic-time algorithm for the diameter
and all eccentricities on median graphs

Pierre Bergé¹,⁴*, Guillaume Ducoffe²,³ and Michel Habib⁴

¹*LIMOS, Université Clermont Auvergne, Clermont Auvergne
INP, CNRS, Mines Saint-Etienne, Clermont-Ferrand, France.

²National Institute for Research and Development in Informatics,
Romania.

³University of Bucharest, Romania.

⁴IRIF, CNRS, Université Paris Cité, France.

*Corresponding author(s). E-mail(s): pierre.berge@uca.fr;

Abstract

On sparse graphs, Roditty and Williams [2013] proved that no $O(n^{2-\epsilon})$-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 combinatorial 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 necessary anymore to determine all eccentricities in subquadratic time. The execution time of our algorithm is $O(n^{1.6456 \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)$.

**Keywords:** Median graphs, Diameter, Eccentricities, Hypercubes
2 *Subquadratic-time algorithm for the diameter on median graphs*

# 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 [1, 2], CAT(0) cube complexes [3, 4], abstract models of
concurrency [5, 6], and genetics [7, 8]. 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 $ecc(v)$ of a vertex $v$ is the maximum length of a shortest path starting from $v$: $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|E|)$, with $n = |V|$. As median graphs
are relatively sparse, $|E| \le n \log n$, these multiple BFSs compute all eccen-
tricities 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 exam-
ple [9–11]. Many works have also been devoted to approximation algorithms
for this parameter. Chechik *et al.* [12] showed that the diameter can be approx-
imated within a factor $\frac{3}{2}$ in time $\tilde{O}(m^{\frac{3}{2}})$ on general graphs. On sparse graphs,
it was shown in [13] that no $O(n^{2-\epsilon})$-time algorithm can achieve an approxi-
mation 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 hyper-
cubes. They are the 1-skeletons of CAT(0) cube complexes [4] and the domains
of event structures [5]. They admit structural properties, such as the Mulder’s
convex expansion [14, 15]. They are strongly related to hypercube retracts [16],
Cartesian products and gated amalgams [3], but also Helly hypergraphs [17].
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: $|E| \le 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 num-
ber $q \le 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 for-
mula $2n - m - q \le 2$ [18]. A recent LexBFS-based algorithm [19] identifies the
$\Theta$-classes in linear time $O(|E|) = O(dn)$.

Two subquadratic-time algorithms have been proposed for the recognition of median graphs. Using convex characterizations of halfspaces, Hagauer et al. [20] showed that median graphs can be recognized in $O(n^{3/2} \log n)$. In [21], a bijection between median and triangle-free graphs makes the recognition algorithms for triangle-free graphs work on median ones [22]. Hence, median graphs can be recognized in $O((n \log^2 n)^{1.41})$ using this reduction.

There exist efficient algorithms for some metric parameters on median
graphs. For example, the median set and the Wiener index can be determined
in $O(|E|)$ [19]. Subfamilies of median graphs have also been studied. There
is an algorithm computing the diameter and the radius in linear time for
squaregraphs [23]. 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 [24], using distance and routing labeling schemes proposed in [25]. Even-
tually, a linear-time algorithm [26] 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 [19, 24]. 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 \{v\}$. These edges form the set $E_K$. All simplex graphs are
median [3, 27]. 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 eccentric-
ities of each vertex of a simplex graph could be written as functions of the size
admit an interesting property: for median graphs with “large” $d$, their number
is subquadratic. This provides us with a better subquadratic-time algorithm for
the eccentricities using the following win-win approach: either the dimension
$d$ of the input graph $G$ is “small” and the linear FPT algorithm is executed
fast, or the dimension is “large”, then the MOPs can be enumerated fast and
our new procedure ensures a smaller runtime.

* There is a combinatorial algorithm determining all eccentricities in $\tilde{O}(n^\beta)$, where $\beta = 1.6456$: Theorem 16, Section 5.2.

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

## 1.3 Organization

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

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

## 2.1 Θ-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
Subquadratic-time algorithm for the diameter on median graphs

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* $ecc(u)$ of a vertex $u \in V$ is the length of the longest shortest path starting from $u$. Put formally, $ecc(u)$ is the maximum value $d(u, v)$ for all $v \in V$: $ecc(u) = \max_{v \in V} d(u, v)$. The diameter of graph $G$ is the maximum distance between two of its vertices: $diam(G) = \max_{u \in V} 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) = \{x \in V : d(u, x) + d(x, v) = d(u, v)\}$. 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[H]$) 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 \ge 1$, the hypercube of dimension $k$, $Q_k$, is a graph representing all the subsets of $\{1, \dots, k\}$ 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 [29], and hypercubes $Q_k$. Median graphs are bipartite and do not contain an induced $K_{2,3}$ [3, 14, 30]. They can be obtained by Mulder's convex expansion [14, 15] starting from a single vertex.

<figure><img src="image_3.png" /><figcaption>**Fig. 1:** Examples of median graphs</figcaption></figure>
Now, we define a parameter which has a strong influence on the study of median graphs. The dimension $d = \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 \le 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 [29], 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 [19–21].

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

**Lemma 1 (Convex$\Leftrightarrow$Gated [3, 19]) Any convex subgraph of a median graph is gated.**

To improve readibility, edges $(u, v) \in E$ are sometimes denoted by $uv$. We recall the notion of $\Theta$-class, which is well explained in [19], 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, \dots, E_q$. Concretely, two edges $uv$ and $u'v'$ belong to the same $\Theta$-class if there is a sequence $uv = u_0v_0, u_1v_1, \dots, u_rv_r = u'v'$ such that $u_iv_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} = \{E_1, \dots, E_q\}$. To avoid confusions, let us highlight that parameter $q$ is different from the dimension $d$: for example, on trees, $d = 1$ whereas $q = n - 1$. Moreover, the dimension $d$ is at most $\lfloor \log n \rfloor$ in general.

**Lemma 2 ($\Theta$-classes in linear time [19]) There exists an algorithm which computes the $\Theta$-classes $E_1, \dots, E_q$ of a median graph in linear time $O(|E|) = O(dn)$**.

In median graphs, each class $E_i$, $1 \le i \le q$, is a perfect matching cutset and its two sides $H'_i$ and $H''_i$ satisfy nice properties, that are presented below.

**Lemma 3 (Halfspaces of $E_i$ [15, 19, 20])** For any $1 \le i \le q$, the graph $G$ deprived of edges of $E_i$, i.e. $G\setminus E_i = (V, E\setminus E_i)$, has two connected components $H'_i$ and $H''_i$, called halfspaces. Edges of $E_i$ form a matching: they have no endpoint in common. Halfspaces satisfy the following properties.

* Both $H'_i$ and $H''_i$ are convex/gated.
* If uv is an edge of $E_i$ with $u \in H'_i$ and $v \in H''_i$, then
  $H'_i = W(u,v) = \{x \in V : d(x,u) < d(x,v)\}$ and $H''_i = W(v,u) = \{x \in V : d(x,v) < d(x,u)\}$.

<figure><img src="image_4.png" /><figcaption>Fig. 2: A class $E_i$ with sets $H'_i, H''_i, \partial H'_i, \partial H''_i$</figcaption></figure>

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

**Lemma 4 (Boundaries [15, 19, 20])** *Both $\partial H'_i$ and $\partial H''_i$ are convex/gated. Moreover, the edges of $E_i$ define an isomorphism between $\partial H'_i$ and $\partial H''_i$.*

As a consequence, suppose $uv$ and $u'v'$ belong to $E_i$: if $uu'$ is an edge and belongs to class $E_j$, then $vv'$ is an edge too and it belongs to $E_j$. We terminate this list of lemmas with a last property dealing with the orientation of edges from a canonical basepoint $v_0 \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 $\overrightarrow{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 [19])** *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$. 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\setminus E_i$. In other words, $u$ and $v$ are in different halfspaces of $E_i$.

The signatures of two vertices provide us with the composition of any shortest $(u, v)$-path. Indeed, all shortest $(u, v)$-paths contain exactly one edge for each class in $\sigma_{u,v}$.

**Lemma 6 ([26]** 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$, 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: $\{E_i : uv \in E_i \cap B\}$. The signature of a path is the set of classes which have at least one edge in this path. In this way, the signature $\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 [31], Kovse studied a relationship between *splits* which refer to the halfspaces of $\Theta$-classes. It says that two splits $\{H'_i, H''_i\}$ and $\{H'_j, H''_j\}$ are *incompatible* if the four sets $H'_i \cap H'_j$, $H''_i \cap H''_j$, $H'_i \cap H''_j$, and $H''_i \cap H''_j$ 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$.
10 *Subquadratic-time algorithm for the diameter on median graphs*

Indeed, classes $E_i$ and $E_j$ are orthogonal if and only if the splits produced by their halfspaces are incompatible.

**Lemma 7** (Orthogonal↔Incompatible [26]) *Given two Θ-classes $E_i$ and $E_j$ of a median graph $G$, the following statements are equivalent:*

* Classes $E_i$ and $E_j$ are orthogonal,

* Splits $\{H'_i, H''_i\}$ and $\{H'_j, H''_j\}$ are incompatible,

* The four sets $\partial H'_i \cap \partial H'_j$, $\partial H''_i \cap \partial H''_j$, $\partial H'_i \cap \partial H''_j$, and $\partial H''_i \cap \partial H''_j$ are nonempty.

The concept of *orthogonality* is sometimes described with different words in the literature depending on the context: incompatible, concurrent or crossing. We say that $E_i$ and $E_j$ are parallel if they are not orthogonal, that is $H_i \subseteq H_j$ for some $H_i \in \{H'_i, H''_i\}$ and $H_j \in \{H'_j, H''_j\}$.

We pursue with a property on orthogonal Θ-classes: if two edges of two orthogonal classes $E_i$ and $E_j$ are incident, they belong to a common square.

**Lemma 8** (Squares [5, 26]) *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 Θ-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 Θ-classes of a median graph form a POF if and only if the graph is a hypercube of dimension $\log n$ [31, 32]. Secondly, the next lemma makes precise the relationship between POFs and hypercubes.

**Lemma 9** (POFs adjacent to a vertex [26]) *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 Θ-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, 31, 33]) 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, $|\mathcal{E}^-(v)| = |N^-(v)| \le 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 = |\mathcal{L}|$.

<figure><img src="image_5.png" /><figcaption>**Fig. 3:** Illustration of the bijection between $V$ and the set of POFs.</figcaption></figure>

<table><thead><tr><th>Vertex</th><th>$v_0$</th><th>$v_1$</th><th>$v_2$</th><th>$v_3$</th></tr></thead><tbody><tr><td>POF</td><td>$\emptyset$</td><td>$\{E_3\}$</td><td>$\{E_1\}$</td><td>$\{E_1, E_3\}$</td></tr></tbody><thead><tr><th>Vertex</th><th>$v_4$</th><th>$v_5$</th><th>$v_6$</th><th>$v_7$</th></tr></thead><tbody><tr><td>POF</td><td>$\{E_4\}$</td><td>$\{E_2\}$</td><td>$\{E_2, E_3\}$</td><td>$\{E_2, E_4\}$</td></tr></tbody></table>

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_1v_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 [7, 31]. Given a basepoint $v_0$, we say that the *basis* (resp. *anti-basis*) of an induced hypercube $Q$ is the single vertex $v$ such that all edges of the hypercube adjacent to $v$ are outgoing from (resp. incoming into) $v$. Said differently, the basis of $Q$ is its closest-to-$v_0$ vertex and its anti-basis is its farthest-to-$v_0$ vertex. What Lemma 10 states is also that we can associate with any POF $X$ a hypercube $Q_X$ which contains exactly the classes $X$ and admits $v_X$ as its anti-basis. This observation implies that the number of POFs is less than the number of hypercubes in $G$. Moreover, the hypercube $Q_X$ is the closest-to-$v_0$ hypercube formed with the classes in $X$. Figure 4a shows a vertex $v$ with its incoming and outgoing edges with the $v_0$-orientation. The dashed edges represent the hypercube with anti-basis $v$ and POF $\mathcal{E}^-(v)$.

**Number of hypercubes.** We recall a formula establishing a relationship between the number of POFs and the number of hypercubes in the literature.
12 Subquadratic-time algorithm for the diameter on median graphs

<figure><img src="image_6.png" /><figcaption>(a) The hypercube “induced” by the edges (b) A POF signing at least two hypercubes $Q$ and $Q'$ is not maximal.</figcaption></figure>

<caption>**Fig. 4: Properties of POFs**</caption>

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 \le d$ in $G$. According to [7, 31], we have:

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

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

**Lemma 11 (Number of hypercubes)** $\alpha(G) \le 2^d n$.

Value $\alpha(G)$ considers all hypercubes, in particular those of dimension 0, i.e. vertices. From now on, the word “hypercube” refers to the hypercubes of dimension at least one.

Each hypercube in the median graph $G$ can be defined with only its anti-basis $v$ and the edges $\tilde{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)$: $\tilde{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 $\tilde{\mathcal{E}}$ of the edges in $\tilde{N}$ (its signature).

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

**Lemma 12 (Enumeration of hypercubes [26])** We can enumerate all triplets $(v, u, \tilde{\mathcal{E}})$, where $v$ is the anti-basis of a hypercube $Q$, $u$ its basis, and $\tilde{\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')$, then any triplet $(v, u, \tilde{\mathcal{E}})$ containing $v$ appears before any triplet $(v', u', \tilde{\mathcal{E}}')$ containing $v'$.
The enumeration of hypercubes is thus executed in linear time for median graphs with constant dimension. In summary, given any median graph, one can compute the set of Θ-classes and their orthogonality relationship (for each $E_i$, the set of Θ-classes orthogonal to $E_i$) in linear time, and the set of hypercubes with its basis, anti-basis and signature in $\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 Θ-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'' \quad (2)$$

As every $\partial H_i''$ is gated, then the intersection written in Eq. (2) is convex/gated too. Thus, the shortest $(v_X, v_Y)$-path is entirely contained in $\bigcap_{X_Q} \partial H_i''$. Let $(v_X, z)$ be the first edge of this path and $E_j$ the Θ-class of this edge. Each Θ-class form an isomorphism between its two boundaries (Lemma 4): as $z \in \bigcap_{X_Q} \partial H_i''$, there is a hypercube isomorphic to $Q$ in the boundary of $E_j$ containing $z$. Therefore, there is a hypercube of dimension $|X_Q| + 1$ containing all vertices of $Q$. This yields a contradiction as $Q$ is supposed to be maximal.

Conversely, let $Q$ be a hypercube and assume that its signature $X_Q$ is a maximal POF. We suppose that there is a second hypercube $Q' \neq Q$ such that $X_Q = X_{Q'}$. Then, the set $\bigcap_{X_Q} \partial H_i''$ contains at least two elements: the anti-bases of hypercubes $Q$ and $Q'$. Using the same argument as above, we can put in evidence an edge with two endpoints in $\bigcap_{X_Q} \partial H_i''$. The Θ-class of this edge is thus orthogonal of any class $E_i$ of $X_Q$ which defines an isomorphism between $\partial H_i'$ and $\partial H_i''$. Consequently, we obtain a POF superset of $X_Q$, a contradiction.

For any POF $X$, there is at least one hypercube with signature $X$ such that its anti-basis $v$ verifies $\mathcal{E}^{-}(v) = X$ according to Lemma 10. In summary, any maximal POF $X$ can be associated with an unique hypercube of signature $X$. $\square$

Figure 4b illustrates this proof with two squares $Q$ and $Q'$ with the same signature $\{E_i, E_h\}$. One can observe the appearance of a hypercube of larger dimension containing $Q$, giving evidence of the non-maximality of $X_Q$.

The number of maximal hypercubes in a median graph is thus equal to the number of maximal POFs, which is itself at most linear in the number of vertices.
# 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 [34]) The simplex graph $K(G) = (V_K, E_K)$ of $G = (V, E)$ is made up of the vertex set $V_K = \{C \subseteq V : C \text{ induced complete graph of } G\}$ and the edge set $E_K = \{(C, C') : C, C' \in V_K, C \subsetneq C', |C'| - |C| = 1\}$.

Observe that the empty clique of $G$ also corresponds to a vertex $v_0$ in $K(G)$. Therefore $v_0$ has degree $n = |V|$ in $K(G)$. Figure 5 shows, as an example, the simplex graph of a $C_5$. Labels indicate the correspondence between vertices and cliques. We note that simplex graphs of cycles are cogwheels, i.e. wheels with a subdivision on each external edge.

The simplex graph of a $n$-complete graph is a hypercube of dimension $n$. More generally, simplex graphs are median [3, 27]. 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).

<figure><img src="image_7.png" /><figcaption>**Fig. 5:** A cycle $C_5$ and its simplex graph $K(C_5)$</figcaption></figure>

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 \le i \le q, \exists v_i \in V(G), v_0v_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'$ such that $G = K(G')$. Let $G'$ 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'$ (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'$. 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'$.

Then, two vertices $u, v$ of $G$ are adjacent if and only if $\mathcal{E}^-(v) = \mathcal{E}^-(u) \cup \{E_i\}$, for some class $E_i$. On one hand, suppose $uv \in E_i$. Assume that there exists $E_j \in \mathcal{E}^-(u) \setminus \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'' \subsetneq H_j''$, $E_i$ cannot be adjacent to $v_0$. Moreover, if $E_h \in \mathcal{E}^-(v) \setminus \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) \setminus \mathcal{E}^-(u) = \{E_i\}$. On the other hand, if $\mathcal{E}^-(v) = \mathcal{E}^-(u) \cup \{E_i\}$, let $v'$ be the vertex such that $v'v \in E_i$. Again, Lemma 8 implies that all $\Theta$-classes incoming into $v$ are also incoming into $v'$, so $\mathcal{E}^-(u) \subseteq \mathcal{E}^-(v')$. Furthermore, if there is some $E_j \notin \mathcal{E}^-(u)$ incoming into $v'$, then it should be parallel to $E_i$, a contradiction. Hence, $v' = u$.

(1) $\Rightarrow$ (2). Assume that $G = K(G')$: 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 $\{E_1\}$ 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'$ 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')$, each $\Theta$-class of $G$ is adjacent to $v_\emptyset$. $\square$
16

Subquadratic-time algorithm for the diameter on median graphs

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 $\{\{E_1, E_2\}, \{E_2, E_3\}, \{E_3, E_1\}\}$: it would produce a simplex graph with 3 squares with basis $v_0$ and sharing pairwise an edge. This graph is $Q_3^-$ (the 3-cube minus a vertex) and is not median. The collection implies that $E_1, E_2, E_3$ are pairwise orthogonal, so $\{E_1, E_2, E_3\}$ should be the maximal POF here.

The most obvious example of median graph which is not simplex is certainly
the path $P_4$. Indeed, it has three $\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) ⇒ (1) reveals the reverse application of K.

**Definition 6** (Crossing graphs [34, 35]) 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 [35], $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 sim-
plex 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 con-
sequence 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) = |\mathcal{E}^{-}(u)|$.

A key result is the fact that the central vertex $v_0$ of the simplex graph
belongs to the interval $I(u, v)$ of any pair $u, v$ satisfying $d(u, v) = \text{ecc}(u)$.

**Lemma 13** Let $u, v \in V(G)$ such that $d(u, v) = \text{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) = |\mathcal{E}^{-}(u)\Delta\mathcal{E}^{-}(v)|$. Let $w$ be the vertex of $G$ such that $\mathcal{E}^{-}(w) = \mathcal{E}^{-}(v)\setminus\mathcal{E}^{-}(u)$. If $\mathcal{E}^{-}(u) \cap \mathcal{E}^{-}(v) \neq \emptyset$, then $d(u, w) = |\mathcal{E}^{-}(u) \Delta \mathcal{E}^{-}(w)| = |\mathcal{E}^{-}(u)| + |\mathcal{E}^{-}(w)| > |\mathcal{E}^{-}(u)\setminus\mathcal{E}^{-}(v)| + |\mathcal{E}^{-}(v)\setminus\mathcal{E}^{-}(u)| = d(u, v)$. So, $d(u, w) > \text{ecc}(u)$, a contradiction. $\square$
<figure><img src="image_8.png" /><figcaption>Fig. 6: Illustration of the contradiction in the proof of Lemma 13.</figcaption></figure>

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

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$ and $v_0 \in H'_i$. Moreover, the distance $d(u, v)$ is exactly $|\mathcal{E}^-(u)| + |\mathcal{E}^-(v)|$ because $|\mathcal{E}^-(u)| = d(v_0, u)$ and $|\mathcal{E}^-(v)| = d(v_0, v)$. So, determining the diameter of a simplex graph $G$ is equivalent to maximizing the sum $|X| + |Y|$, where $X$ and $Y$ are two POFs of $G$ that are disjoint. Computing the diameter is equivalent to finding the largest pair of disjoint cliques in the crossing graph $G^\#$. Similarly, the eccentricity of a vertex $u$ is exactly the size $|\mathcal{E}^-(u)| + |\mathcal{E}^-(v)|$ 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 $\mathcal{OP}(X)$ the opposite of $X$, i.e. the POF $Y$ disjoint from $X$ with the maximum cardinality.

$$ \mathcal{OP}(X) = \underset{Y \cap X = \emptyset}{\operatorname{argmax}} |Y|. $$

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

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

**Definition 8 (OPP)**

**Input:** Simplex graph $G$, central vertex $v_0$.

**Output:** For each POF $X$, its opposite $\mathcal{OP}(X)$.
18 *Subquadratic-time algorithm for the diameter on median graphs*

We define an even larger version of the problem where a positive inte-
ger 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} \to \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 func-
tion. 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 [26].

**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 sim-
plex graph $G$ with a central vertex $v_0$ and a weight function $\omega : \mathcal{L} \to \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 [36, 37]. 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[a]$. To improve the readibility, index $(E[a], \text{true})$ will be denoted
by $+E[a]$ while $(E[a], \text{false})$ becomes $-E[a]$.

We denote by $\mathcal{L}[E_i]$ 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|\mathcal{L}|$.

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 exam-
ple based on their index. Let $E_{i_1}, E_{i_2}, \dots, E_{i_r}$ be the classes of $L_0$ ordered,
$|L_0| = 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}[E_{i_1}]$ and its com-
plementary. 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^{|L_0|}$
sets in the partition.

Until now, we obtained the top $r$ levels of tree $T$. Before pursuing the
construction, we define some notations. Let $a_0$ be the root of $T$. Node $a_0$
represents the entire collection $\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}[E_{i_1}]$ 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 $\Theta$-classes we can find on 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) = \{E_{i_1}, E_{i_2}\}$. 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) = \{E_{i_2}\}$ and $R^-(a) = \{E_{i_1}\}$. 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
(deepth at most $d$) that we call *blocks*. For example, the root $a_0$ of $T$ belongs to
20 *Subquadratic-time algorithm for the diameter on median graphs*

the top block which is produced from the partition refinement over Θ-classes
of L₀. In Figure 7a, we represent some nodes a of this block and their index
Lₐ with |L₀| = 3: i₁ = i, i₂ = j, and i₃ = ℓ. The leaves of this block both
belong to the top block and are the roots of another block below this one.

<figure><img src="image_9.png" /><figcaption>(a) Some nodes of T obtained with the partition refinement over L₀</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(b) Some blocks of T: all blocks of layer 0 and 1, one block of layer 2. Node a has layer 2.</figcaption></figure>

<caption>**Fig. 7:** An example of tree *T*: its first block and structure</caption>

Algorithm 1 provides us with the pseudocode of a partition refinement pro-
cedure. We call it Ordered Internal Partition Refinement (OIPR). We execute
OIPR to obtain tree *T* with the following input: the ground set contains the
Θ-classes of *G* (*W* = *E*), the collection is made up of the POFs outgoing from
*m* with the *v*₀-orientation (*S* = *L*) and the ordering of the sets come from
the POFs weights ($\tau = \tau_{\omega}$). Each while loop (line 4) corresponds to the construction of a block of $T$. Such step starts by picking up the first element, say $L_a$, of a non-singleton set of $\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 7). 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 8).

1: **Input:** ground set $W = \{w_1, \dots, w_q\}$, collection $\mathcal{S} = \{S_1, \dots, S_N\}$, $S_i \subseteq W$ for any $1 \le i \le 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 \{\mathcal{S}\}$, partition with a single set;

4: **while** there exists a part of $\mathcal{P}$ which is not a singleton **do**

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

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

7: &nbsp;&nbsp;&nbsp;&nbsp;**for** every $w_j \in A$ non locally visited **do**

8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Substitute $Q$ in $\mathcal{P}$ by $\text{Refine}(Q, \{w_j\})$;

9: **endfor**
end

**Algorithm 1:** Ordered Internal Partition Refinement (OIPR)

The time needed to run Algorithm 1, using a doubly linked list data structure, depends on the number of appearances of each element $w_j$ of the ground set into the collection $\mathcal{S}$.

**Lemma 14** (Execution time of OIPR [36]) 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}[E_j]$. We explained above why the total size of these adjacency lists could not exceed $dn$.

**Corollary 2** *Computing order $\tau_{\omega}$ and then OIPR applied with $W = \mathcal{E}$, $\mathcal{S} = \mathcal{L}$ and $\tau = \tau_{\omega}$ can be done 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. $\square$

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[a]$; 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 = |\mathcal{L}|$. We say the *layer* of a node $a$ is the number of blocks we pass through when we traverse the simple path between the root and $a$ minus 1. For example, the root has layer 0 and the leaves of the top block have layer 1. We denote by $T^{(j)}$, $j \ge 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[a]$ 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 \{E[a]\}$ is not a POF, then there is no POF superset of $R^+(a) \cup \{E[a]\}$.

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$, like 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 of $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) = \text{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[a]$ (resp. $-E[a]$) in T (Figure 8). We define the set $C(a, X)$ which describes the recursive calls needed to compute $h(a, X)$. Formally, the objective is to make sure that value $h(a, X)$ is exactly a function of all $h(a', X')$, where $(a', X') \in C(a, X)$. The construction of set $C(a, X)$ is described below. We distinguish four cases: A, B, C, and D.

<figure><img src="image_11.png" /><figcaption>Fig. 8: Nodes a, $a^+$ and $a^-$ in tree T.</figcaption></figure>

* **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: $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[a]$ belongs to $X$: $E[a] \in X$. Otherwise, see next cases. As $R(a^-) = R(a) \cup \{E[a]\}$, $(a^-, X \setminus E[a])$ is a constraint pair (Definition 10): $R(a^-) \cap (X \setminus E[a]) = \emptyset$ and $R^+(a^-) = R^+(a)$ is orthogonal to all $\Theta$-classes of set $X \setminus E[a]) \subsetneq X$. We fix $C(a, X)$ as a singleton containing $(a^-, X \setminus E[a])$: $C(a, X) = \{(a^-, X \setminus E[a])\}$.

* **Case C.** Set $E[a] \cup X$ is a POF: $E[a] \cup X \in \mathcal{L}$. As $E[a] \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 C$. Second, $R^+(a^+) = R^+(a) \cup E[a]$; as $E[a]$ is orthogonal to all $\Theta$-classes of $X$, $R^+(a^+) \cup X$ is a POF and $(a^+, X) \in C$. These two constraint pairs are the elements of $C(a, X)$: $C(a, X) = \{(a^+, X), (a^-, X)\}$.

* **Case D.** Set $E[a] \cup X$ is not a POF: $E[a] \cup X \notin \mathcal{L}$. Let $X_{|E[a]} \subsetneq X$ be the $\Theta$-classes of $X$ which are orthogonal to $E[a]$. Pair $(a^-, X)$ is a constraint pair, using the same arguments as in Case C. We verify whether another pair $(a^+, X_{|E[a]}) \in C$. As $X_{|E[a]} \subsetneq X$ and $E[a] \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[a]$ is a POF by definition, so $X_{|E[a]} \cup R^+(a^+)$ is a POF. We fix $C(a, X) = \{(a^-, X), (a^+, X_{|E[a]})\}$.

Observe that when $(a', X') \in C(a, X)$, then $a$ is a parent of $a'$ in T. Moreover, $X' \subseteq X$. The size of all sets of recursive calls $C(a, X)$ is at most two. The
24 Subquadratic-time algorithm for the diameter on median graphs

following theorem justifies that POF $h(a, X)$ can be determined as a function of all $h(a', X')$ satisfying $(a', X') \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) = \underset{h(a', X') \text{ s.t. } (a', X') \in \mathcal{C}(a, X)}{\operatorname{argmax}} \omega(h(a', X')) \quad (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[a] \in X$. Recall that $\mathcal{C}(a, X) = \{(a^{-}, X \setminus E[a]\}$ in this case. POF $h(a, X)$, which is disjoint from $X$, cannot contain class $E[a]$. As a consequence, $h(a, X)$ belongs to $\Omega(a^{-})$ which is made up of the POFs of $\Omega(a)$ without $E[a]$. Moreover, $h(a, X)$ does not contain any class of $X \setminus E[a]$. We have: $h(a, X) = h(a^{-}, X \setminus E[a])$.

In Case C, we assume that $E[a] \cup X$ is a POF. As $E[a] \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) = \{(a^{-}, X), (a^{+}, X)\}$.

In Case D, we assume that $E[a] \cup X$ is not a POF. As in Case C, $E[a] \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 \setminus X_{|E[a]}$. Classes $E_h$ and $E[a]$ are parallel, otherwise $E_h$ would belong to $X_{|E[a]}$. All POFs of set $\Omega(a^{+})$ contain $E[a]$, 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 \setminus 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) = \{(a^{-}, X), (a^{+}, X_{|E[a]})\}$. $\square$

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 $\mathbf{op}(L) = h(a_0, L)$ and $\mathbf{op}(\hat{L}) = h(a_0, \hat{L})$: dotted lines mean there is a path between two pairs.

We observe that the constraint pairs of $V(H)$ are made up of nodes of $T^{(d)}$.
<figure><img src="image_12.png" /><figcaption>Fig. 9: Some vertices of the DAG H</figcaption></figure>

**Lemma 15** *Constraint pairs $(a, X)$ in $V(H)$ satisfy the following inequality: $|X| \le d - \text{layer}(a)$.*

*Proof* We proceed by induction. The roots of the DAG, i.e. the constraint pairs $(a_0, X)$, verify this inequality, as $\text{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', X')$ and an arc going from it to $(a, X)$, such that $\text{layer}(a) = \text{layer}(a') + 1$. We select a pair $(\hat{a}', \hat{X}')$ in $V(H)$ which is an ancestor of $(a', X')$ - there is a directed path from $(\hat{a}', \hat{X}')$ to $(a', X')$ in $H$ - and such that $\hat{a}'$ is the ancestor of $a'$ in $T$ which is at the top of the block $B_{\hat{a}'}$ of layer $\text{layer}(a')$ containing $a'$. Thus, node $a$ is a leaf of block $B_{\hat{a}'}$. The existence of a directed path in $H$ from $(\hat{a}', \hat{X}')$ to $(a, X)$ means that the recursive computation of $h(\hat{a}', \hat{X}')$ uses the term $h(a, X)$. The POF $L_{\hat{a}'}$ is not disjoint from $\hat{X}'$ otherwise pair $(\hat{a}', \hat{X}')$ would be a leaf in $H$ (Case A). Let $E_h \in L_{\hat{a}'} \cap \hat{X}'$. As $a$ is a leaf of the block $B_{\hat{a}'}$, it verifies $E_h \in R(a)$ by construction of $T$. As $(\hat{a}', \hat{X}')$ is an ancestor of $(a, X)$, then $X \subseteq \hat{X}'$. But $(a, X)$ is a constraint pair and $E_h \in R(a)$, so $X \subseteq \hat{X}' \setminus \{E_h\}$. In brief, $|X| \le |\hat{X}'| - 1$. Using the induction hypothesis, $|X| \le d - \text{layer}(\hat{a}') - 1 = d - \text{layer}(a)$.

Second, suppose that all predecessors $(a', X')$ of $(a, X)$ satisfy $\text{layer}(a') = \text{layer}(a)$. As $X \subseteq X'$, $|X| \le |X'| \le d - \text{layer}(a') = d - \text{layer}(a)$. $\square$

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 subsection 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^3n)$. The global algorithm is divided into two parts.

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. Computation of all opposites $h(a_0, L)$ with DP.

The runtime needed to build $T^{(d)}$ is $O(d^2n)$. 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^2n)$ 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 $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^2n$ constraint pairs in $C^{(d)}$.*

*Proof* We define a function $f: \mathcal{L} \to 2^C$ such that, for any $L \in \mathcal{L}$, $|f(L)| \le d^2$. We show that for any constraint pair $(a, X) \in 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^2n$, we have $|C^{(d)}| \le d^2n$.

**- Step 1: definition of function $f$.** Our method consists in defining an *itinerary* function $I: C^{(d)} \to C^{(d)}$, where $(a, X) = I(a', X')$ implies that $X \subseteq X'$ and $a$ is a child of $a'$ 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) = \{(a_0, Y), I(a_0, Y), I(I(a_0, Y)), \dots\}$. As the depth of $T^{(d)}$ is at most $d^2$, we confirm that $|f(Y)| \le d^2$.

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

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

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

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

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

**- Step 2: any constraint pair is generated by $f$.** We show that any $(a, X) \in C^{(d)}$ can be written as $I^k(a_0, Y)$ for some POF $Y \supseteq X$ and $0 \le k < d^2$. We proceed
<figure><img src="image_13.png" /><figcaption>**Fig. 10:** Nodes *a*, *a'*, and *a*\* in *T* when *a'* is not the root of a block in Scenario 1. Blue arrows indicate the successive appliances of the itinerary function on (*a*₀, *Y*).</figcaption></figure>

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

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

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

We show that $I(a', X') = (a, X)$. We refer to Case B*: the Θ-class $E[a']$ belongs to $X'$, so function *I* returns $(a^-, X' \setminus \{E[a']\}) = (a, X)$.
• **Scenario 2:** edge $(a', a)$ in $T$ is indexed by $-E[a']$ and $X \cup E[a']$ is not a POF.

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

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

• **Scenario 3:** edge $(a', a)$ in $T$ is indexed by $+E[a']$.

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

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

In summary, there is a constraint pair $(a', X')$ such that $a'$ is the parent of $a$, $X \subseteq X'$, and $I(a', X') = (a, X)$. The induction hypothesis terminates the proof of our claim: as $(a', X')$ is in some itinerary $f(Y)$ with $X' \subseteq Y$, and $I(a', X') = (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$. $\square$

The size of the state space of the DP procedure is at most $O(d^3 n)$ because $|h(a, X)| \le 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 + \log n)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 [26] 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^{5/3})$.
## 4.1 Linear FPT algorithm for constant-dimension median graphs

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

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

Some parts of this subsection are redundant with [26], however we keep this subsection self-contained. The new outcomes presented are Theorems 7 and 9. The results that are reminded will also be useful for Section 5.

The algorithm evoked by Lemma 16 consists in the computation of three kinds of labels: ladder labels $\varphi$, opposite labels $\text{op}$ and anti-ladder labels $\psi$. The order in which they are given correspond to their respective dependence: $\text{op}$-labelings are functions of labels $\varphi$ and $\psi$-labelings are functions of both labels $\varphi$ and $\text{op}$. The definition of $\text{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 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 11 (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}$.

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 recall 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 additionally 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})$.
30

Subquadratic-time algorithm for the diameter on median graphs

<figure><img src="image_14.png" /><figcaption>Fig. 11: Examples of ladder sets: $L_{u,v} = \{E_2, E_3\}$, $L_{u,x} = \{E_1, E_2, E_3\}$.</figcaption></figure>

**Lemma 17** ([26]) 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 \le i \le |L_{u,v}|$, the $i^{th}$ first edge of the path belongs to the $i^{th}$ $\Theta$-class of $L_{u,v}$ in ordering $\tau$.

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

**Definition 12** (Labels $\varphi$ [26]) 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. We provide another notion related to orthogonality which will be used in the remainder.

**Definition 13** (*L*-parallelism) We say that a POF $L'$ is *L*-parallel if, for any $E_j \in L'$, $L \cup \{E_j\}$ is not a POF.

When $L'$ is a $L$-parallel POF, we have $L \cap L' = \emptyset$, otherwise $L \cup \{E_j\} = L$ for some $E_j \in L'$. Presented differently, a $L$-parallel POF is such that any of its $\Theta$-classes is parallel to at least one $\Theta$-class of $L$.

A combinatorial algorithm running in $\tilde{O}(2^{2d}n)$ which computes all labels $\varphi(u, L)$ was identified in [26]: 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$ [26]) 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^+$ satisfies $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$-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) = |L|$: 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)$.

$$ \varphi(u, L) = \max_{\substack{L^+ \text{ POF outgoing from } u^+ \\ \forall E_j \in L^+, L \cup \{E_j\} \text{ not POF}}} (|L| + \varphi(u^+, L^+)). \quad (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. Briefly, the algorithm consists in listing all pairs vertex-ladder set $((u, L), (u^+, L^+))$ such that $u^+$ is the anti-basis of the hypercube of basis $u$ and signature $L$. For each of them, we verify whether $L^+$ is $L$-parallel. If it is, we update $\varphi(u, L)$ if $|L| + \varphi(u^+, L^+) > \varphi(u, L)$ is greater than the current value. The total number of pairs $((u, L), (u^+, L^+))$ is upper-bounded by $2^{2d}n$: there are at most $2^d n$ pairs $(u^+, L^+)$ (bijection with hypercubes) and, for each of them, there are at most $2^d$ compatible pairs $(u, L)$ such that $u^+$ is the anti-basis of $(u, L)$. Indeed, the number of edges incoming into $u^+$ is at most $d$ (Lemma 10). For this reason, the computation of $\varphi$-labelings takes $\tilde{O}(2^{2d}n)$.

**Theorem 6 (Computation of labels $\varphi$ [26])** 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.2 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 $\mathbf{op}$ defined in Section 3 for simplex graphs. Given a vertex $u$ and a POF $L$ outgoing from $u$, let $\mathbf{op}_u(L)$ denote a POF with maximum label $\varphi$ which is disjoint from $L$. As for $\varphi$, the total size of $\mathbf{op}$-labelings is $O(2^d n)$.

**Definition 14 (Labels $\mathbf{op}$ [26])** Let $u \in V$ and $L$ be a POF outgoing from $u$. Let $\mathbf{op}_u(L)$ be one of the POF $L'$ outgoing from $u$, disjoint from $L$, which maximizes value $\varphi(u, L')$.

On simplex graphs, the opposite function provides in fact the $\mathbf{op}$-labelings of vertex $v_0$: $\mathbf{op}(X) = \mathbf{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 $\mathbf{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 [26]) Let $L, L'$ 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'$). Then, $u \in I(s,t)$ if and only if $L \cap L' = \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, \mathbf{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, \mathbf{op}_u(L))$, where $L$ is POF outgoing from $u$.

An algorithm was initially proposed to compute all labels $\mathbf{op}_u(L)$ consisting in a brute force bounded tree search [26]. 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[V_u]$ be the star graph of $u$, using a definition from [25]. 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. [25] showed that graph $G_u$ is a gated/convex subgraph of $G$. This notion of star graph is essential for the proof of the following key theorem.

**Theorem 7** (Computation of labels $\mathbf{op}$) There is a combinatorial algorithm which determines all labels $\mathbf{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.

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, $|V_u| = 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 $\mathbf{op}_u(L)$: a POF $L'$ disjoint from $L$ and maximizing $\varphi(u, L')$ among all POFs outgoing from $u$. The running time of the algorithm is $O((d^3 + \log |V_u|)|V_u|) = O((d^3 + \log n)N_u)$.
<figure><img src="image_15.png" /><figcaption>Fig. 12: Example of star graph $G_u$</figcaption></figure>

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). $\square$

### 4.1.3 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 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 15** (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) = \{u, v\}$. Otherwise, the set $\Pi(u, v)$ is the union of $\Pi(u^+, v)$ with vertex $u$: $\Pi(u, v) = \{u\} \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 16** (Penultimate milestone $\bar{\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 $\bar{\pi}(u, v)$. Furthermore, we denote by $\bar{L}_{u,v}$ the anti-ladder set of $u, v$, i.e. the $\Theta$-classes of the hypercube with basis $\bar{\pi}(u, v)$ and anti-basis $v$.
34

<figure><img src="image_16.png" /><figcaption>**Fig. 13:** A pair $u, v$ with $u \in I(v_0, v)$ and its milestones $\Pi(u, v)$ in red.</figcaption></figure>

Figure 13 shows the milestones $\Pi(u, v) = \{u, u^+, u^{++}, v\}$. The hypercubes with the following pair basis-signature are highlighted with dashed edges: $(u, L_{u,v})$, $(u^+, L_{u^+,v})$, and $(u^{++}, L_{u^{++},v})$. We have $\pi(u, v) = u^{++}$ and $\bar{L}_{u,v} = L_{u^{++},v}$ is drawn with dashes 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 17** (Labels $\psi$ [26]) 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: \bar{L}_{m,u} = R$.

Equivalently, vertex $u^-$ is the penultimate milestone of pair $m, u: u^- = \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 $\text{op}_{v_0}(R)$ of $R$ which is outgoing from $v_0$. Hence, $\psi(u, R) = |R| + \varphi(v_0, \text{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) = \{u^-, u\}$. A shortest $(u, v)$-path is the concatenation of the shortest $(u, u^-)$-path of length $|R|$ with a shortest $(u^-, v)$-path, and $u^- \in I(v_0, v)$. The largest distance $d(u, v)$ we can have, as for the base case, is $\psi(u, R) = |R| + \varphi(u^-, \text{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$ [26]) 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:

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

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

(iii) the POF $L$ is $\bar{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 \{E_j\}$ is not a POF, for each $E_j \in R$. For this reason, value $\psi(u, R)$ can be expressed as:

$$ \psi(u, R) = \max_{\substack{R^- \text{ POF incoming to } u^- \\ \forall E_j \in R, R^- \cup \{E_j\} \text{ not POF}}} (|R| + \psi(u^-, R^-)) \quad (5) $$

Our algorithm consists in taking the maximum value between the two cases. The number of pairs $((u, R), (u^-, R^-))$ which satisfy the condition described in Equation (5) is at most $2^{2d}n$: it is identical to the one presented for $\phi$-labelings.

**Theorem 8** (Computation of labels $\psi$ [26]) There is a combinatorial algorithm which determines all labels $\psi(u, R)$ in $\bar{O}(2^{2d}n)$.

### 4.1.4 Better time complexity for all eccentricities

The computation of all labels $\varphi(u, L)$, $\mathrm{op}_u(L)$ and $\psi(u, R)$ gives an algorithm which determines all eccentricities. Indeed, each eccentricity $\mathrm{ecc}(u)$ is a function of certain labels $\varphi$ and $\psi$. Let $v$ be a vertex in $G$ such that $\mathrm{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:

$$ \mathrm{ecc}(u) = \max \left\{ \begin{array}{ll} \max_{\substack{L \text{ POF} \\ \text{outgoing from } u}} \varphi(u, L), & \max_{\substack{R \text{ POF} \\ \text{incoming to } u}} \psi(u, R) \\ & \end{array} \right\} \quad (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 9** (All eccentricities in $\tilde{O}(2^{2d}n)$-time for median graphs) *There is a com- binatorial 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 6, 7, and 8. Thanks to the time improvement obtained for the computation of opposite labels, the overall running time to compute the labels is only $\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 \le 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^{O(d)}n$, with $d$ being the dimension (Theorem 9). 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 \le 1$. By doing so, we obtain (in combination with Theorem 9) the first known subquadratic-time algorithm for computing all eccentricities in a median graph.

We start with a simple relation between the eccentricity function of a median graph and the respective eccentricity functions of any two complementary halfspaces.

**Lemma 21** Let $G$ be a median graph. For every $1 \le i \le q$, let $v \in V(H'_i)$ be arbitrary, and let $v^*$ be its gate in $\partial H''_i$. Then, $\mathrm{ecc}(v) = \max\{\mathrm{ecc}_{H'_i}(v), d(v, v^*) + \mathrm{ecc}_{H''_i}(v^*)\}$.

*Proof* We have $\mathrm{ecc}(v) = \mathrm{ecc}_G(v) = \max\{d(u, v) \mid u \in V(H'_i)\} \cup \{d(w, v) \mid w \in V(H''_i)\}$. Since $H'_i$ is convex, we have $\max\{d(u, v) \mid u \in V(H'_i)\} = \mathrm{ecc}_{H'_i}(v)$. In the same way, since $H''_i$ is gated (and so, convex), we have $\max\{d(w, v) \mid w \in V(H''_i)\} = d(v, v^*) + \max\{d(v^*, w) \mid w \in V(H''_i)\} = d(v, v^*) + \mathrm{ecc}_{H''_i}(v^*)$. □

We will use this above Lemma 21 later in our proof in order to compute in linear time the list of eccentricities in a median graph being given the lists of eccentricities in any two complementary halfspaces.

Next, we give simple properties of $\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$. $\square$

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

**Lemma 23** Let $H$ and $G$ be median graphs, and let $E_1, E_2, \dots, 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 \le i \le q$.

*Proof* It is known [38] 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$. $\square$

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 \le i \le q\}$ be the maximum cardinality of a $\Theta$-class of $G$. Then, $d = \dim(G) \le \lfloor \log D \rfloor + 1$.

*Proof* Any induced $d$-dimensional hypercube of $G$ contains exactly $2^{d-1}$ edges of its $\Theta$-classes. $\square$

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, \dots, 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, \dots, E_p$ to be the subset of all $\Theta$-classes of cardinality $\ge D$, for some $p \le q$. Note that we have $p \le 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 \dots \cup E_p)$. More formally, we construct a rooted binary tree$^1 T$, whose leaves are labelled with convex subgraphs of $G$. Initially, $T$ is reduced to a single node with label equal to $G$. Then, for $i = 1 \dots p$, we further refine this tree so that, at the end of any step $i$, its leaves are labelled with

<footnote>$^1$This tree $T$ is independent to the one built in Section 3.2</footnote>
the connected components of $G \setminus (E_1 \cup E_2 \cup \dots \cup E_i)$. 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 \dots \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)$.

<figure><img src="image_17.png" /><figcaption>Fig. 14: An example of tree $T$ associated with a graph $G$ for $D = 3$: here, $p = 2$.</figcaption></figure>

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

* If $H$ labels a leaf (base case) then, we claim that we have $\dim(H) \le \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, H''_i$ be its children nodes, obtained from the removal of $E(H) \cap E_i$ for some $1 \le i \le 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, H''_i$ are gated subgraphs. By Lemma 21, we can compute in $O(|V(H'_i)|)$ time the eccentricities in $H$ of all vertices in $H'_i$ if we are given as input: the list of eccentricities in $H'_i$, the list of eccentricities in $H''_i$, and for every $v \in V(H'_i)$ its gate $v^* \in \partial H''_i$ and the distance $d(v, v^*)$. The respective lists of eccentricities for $H'_i$ and $H''_i$ were pre-computed by dynamic programming on $T$. Furthermore, we can compute the gate $v^*$ and $d(v, v^*)$ for every vertex $v \in V(H'_i)$, in total $\tilde{O}(|V(H)|)$ time, by using a modified BFS rooted at $H''_i$ (we refer to [25, Lemma 17] for a detailed description of this standard
procedure). Overall (by proceeding the same way for $H_i''$ as for $H_i'$) we can compute the list of eccentricities for $H$ in $\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}}$. $\square$

**Theorem 10** 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 9 with Lemma 25 (applied for $c = 4$). $\square$

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.

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

## 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* $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 [28]. The relationship between reach centrality and the well-known metric parameters has been studied: Abboud et al. [39] proved that determining the diameter and the reach centrality are equivalent under subcubic reductions. The formal definition of $RC(u)$ follows.
40 Subquadratic-time algorithm for the diameter on median graphs

$$ \mathrm{RC}(u) = \max_{u \in I(s,t)} \min \{d(s, u), d(u, t)\} \quad (7) $$

In Theorem 9, 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 11** 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 $\bar{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 $\bar{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$. As $E_i \in \sigma_{u,s}$, any shortest $(u, s)$-path contains an edge of $E_i$. Let $(u', v')$ be one of these edges of $E_i$ which is as close as possible from $u$. Vertex $u'$ - the endpoint of this edge closer to $u$ - belongs to $\partial H'_i$. Moreover, there is a shortest $(u, s)$-path $P_{u,s}$ passing through $(u', v')$ because $v'$ is the gate of $u$ in $H''_i$. As $u \in I(v_0, s)$ and $u' \in I(u, s)$, then $u \in I(v_0, u')$. We know that both $v_0$ and $u'$ belong to $H'_i$: by convexity of halfspaces, $u \in H'_i$.

*Claim 2:* $u \in H''_i$. 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} \setminus 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 \{E_i\}$. We have $v', z \in \partial H''_i$. As $v'$ is the gate of $u$ in $H''_i$, there is a shortest $(u, z)$-path passing through $(u', v')$. We denote by $\partial H''_R$ the intersection of all $\partial H''_j$ for all $E_j \in R$. As $u, z \in \partial H''_R$, which is convex, all vertices metrically between $u$ and $z$ belong to $\partial H''_R$, in particular $v'$. The ladder set of $u, v'$ is the same as $u, s$ because $v'$ does not belong to the hypercube $Q_{u,L}$ of basis $u$ and signature $L: L_{u,v'} = L$. In brief, $Q_{u,L} \subsetneq I(u, v')$. 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 \subsetneq H''_j$. Suppose, by way of contradiction, that $E_i \in \sigma_{m,t}$. Vertex $t$ is in
$H_i''$, so it is also in $H_j''$. As $E_j \in R \subseteq \sigma_{m,u}$, then $m \in H_j'$: $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''$.

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)$. $\square$

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) = \text{RC}(u)$, for any vertex $u$. To start, we fix all $\chi(u)$ equal to 0. Let $\xleftarrow{\max}$ be the operator which modifies 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\{\chi(u), a\}$. 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, \text{op}(L_{u,s}))$, according to Lemma 19. If $d(u, s) \le \varphi(u, L_{u,s}) \le \varphi(u, \text{op}_u(L_{u,s}))$, then distance $d(u, s)$ has no influence on $\text{RC}(u)$ as another candidate - any vertex at distance $\varphi(u, L_{u,s})$ from $u$ - overpasses it. Moreover, if $d(u, s) \le \varphi(u, \text{op}_u(L_{u,s})) \le \varphi(u, L_{u,s})$, then $d(u, s)$ also cannot be equal to $\text{RC}(u)$ because $\varphi(u, \text{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, \text{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) \le 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, \text{op}_u(L))$, then modify the label $\chi(u) \xleftarrow{\max} \varphi(u, L)$, otherwise do nothing.

**Step 2: Reach when $u \ne 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 11 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) \ge d(u, s)$ and $\psi(u, R) \ge 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 \ne m = m(s, t, v_0)$ and is not a milestone of $m, s$.** Let $u'$ be the milestone of $\Pi(m, s)$ and $u''$ its successor in $\Pi(m, s)$ such
that $u$ belongs to the hypercube of basis $u'$, anti-basis $u''$ and, hence, signature
$L = L_{u',u''} = \sigma_{u',u''}$. We distinguish two cases.

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

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

- Case 2: $u'$ is not the median of $s, t, v_0$. Let $R$ be the anti-ladder set of $m, u'$. Theorem 11 implies the existence of a pair of vertices $s^*, t^*$ with the same (anti-)ladder sets $L$ and $R$ than $u'$ with $s, t$ and such that $d(u', s^*) = \varphi(u', L)$ and $d(u', t^*) = \psi(u', R)$. Furthermore, Lemma 17 ensures us that a shortest path between $u'$ and $s^*$ can be prefixed with the $\Theta$-classes of $L$ in any ordering. As a consequence, there is a shortest $(u', s^*)$-path containing $u$. As $\varphi(u', L) - d(u', u) \ge d(u, s)$ and $\psi(u', R) + d(u', u) \ge d(u, t)$, the reach centrality of $u$ in this step can be written only as a function of $\varphi, \psi$-labelings and distance $d(u, u')$.

For any pair $L, R$ of POFs respectively outgoing from and incoming to some $u' \in V$ such that $L$ is $R$-parallel: enumerate all vertices $u$ belonging to the hypercube of basis $u'$ and signature $L$. For each of them, if $\varphi(u', L) - d(u', u) < \psi(u, R) + d(u', u)$, we modify the label $\chi(u) \stackrel{\text{max}}{\rightleftarrows} \varphi(u', L) - d(u', u)$. Otherwise, we set $\chi(u) \stackrel{\text{max}}{\rightleftarrows} \psi(u', R) + d(u', u)$.

**Pseudocode.** Algorithm 2 provides us with the pseudocode of this pro-
cedure. The steps corresponding to the updates of $\chi(u)$ are mentioned as
comments, surrounded by symbol #.

The computation of all labels $\varphi$, $\text{op}$, and $\psi$ is a necessary preprocessing of
this algorithm. We remind the reader that they can be obtained in $\tilde{O}(2^{2d}n)$.
Steps 1, 2 and 3 cover all possible configurations of triplet $u, s, t$ such that
$\text{RC}(u) = \min\{d(s, u), d(s, t)\}$. Indeed, either $u$ is the median of $s, t, v_0$ (Step 1)
or not. If not, it is either a milestone of at least one pair among $(m(s, t, v_0), s)$
and $(m(s, t, v_0), t)$ (Step 2), or not (Step 3). In each situation, both distances
$d(s, u)$ and $d(u, t)$ are upper-bounded in function of some label values. Con-
versely, these upper bounds correspond to the distance between $u$ and certain
vertices $s^*, t^*$, such that $u \in I(s^*, t^*)$. Hence, $\text{RC}(u)$ can be expressed as a
function of labelings $\varphi$, $\text{op}$, and $\psi$, as described in Algorithm 2.

**Theorem 12** *There is a combinatorial algorithm computing all reach centralities* $\text{RC}(u)$ *of a median graph in } \tilde{O}(2^{3d}n)$.

*Proof* The correctness of Algorithm 2 is now clear. We focus on its runtime. The most expensive part corresponds to Step 3, Case 2 (line 14). Indeed, we enumerate all triplets $(u, L, R)$: we know they are at most $2^{2d}n$. For each of them, we list all
1: **Input:** Median graph $G$, weight function $C: V \to \mathbb{N}$, labels $\varphi, op, \psi$.

2: **Output:** Labels $\chi(u)$ for any vertex $u \in V$.

3: Initialize $\chi(u) \leftarrow 0$ for any vertex $u$;

4: **for** every pair $(u, L)$ where $L$ is a POF outgoing from $u$ **do**

5: **if** $\varphi(u, L) < \varphi(u, op_u(L))$ **then**

6: $\chi(u) \leftarrow \max \varphi(u, L)$; # Step 1 #

7: **end if**

8: **for** every vertex $u^*$ belonging to the hypercube of basis $u$ and signature $L$ **do**

9: $\chi(u^*) \leftarrow \min \{\varphi(u, L) - d(u, u^*), \varphi(u, op_u(L)) + d(u, u^*)\}$; # Step 3-1 #

10: **end for**

11: **for** every POF $R$ incoming into $u$ such that $L$ is $R$-parallel **do**

12: $\chi(u) \leftarrow \max \{\varphi(u, L), \psi(u, R)\}$ # Step 2 #;

13: **for** every vertex $u^*$ belonging to the hypercube of basis $u$ and signature $L$ **do**

14: $\chi(u^*) \leftarrow \min \{\varphi(u, L) - d(u, u^*), \psi(u, R) + d(u, u^*)\}$; # Step 3-2 #

15: **end for**

16: **end for**

17: **end for**

**Algorithm 2:** Computation of labels $\chi$

vertices lying on the hypercube of basis $u$ and signature $L$, which contains potentially $2^d$ vertices. The total number of 4-uplets $(u, L, R, u^*)$ considered in line 14 of Algorithm 2 is thus at most $2^{3d}$. $\square$

## 5.2 MOP structure

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

### 5.2.1 Definition and relationship with labelings

Recall that a pair made up of a vertex $u$ and a POF $L$ outgoing from this vertex can be seen as a hypercube (of basis $u$ and signature $L$, which is unique). The MOPs are defined to highlight certain hypercubes which satisfy a maximality property.
**Definition 18** (Maximal Outgoing POFs) Pair $(u, L)$ is a MOP if $L$ is outgoing from $u$ and there is no other $L' \supsetneq L$ outgoing from $u$.

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

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

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

**Theorem 13** Assume graph $G$ has at most $\tilde{O}(f(d,n)n)$ MOPs, $f(d,n) = o(2^d)$. There is a combinatorial algorithm computing all labels $\varphi(u, L)$, $op_u(L)$, and $\psi(u, R)$ in $\tilde{O}(2^d f(d,n)n)$.

*Proof* Let $u \in V$, $N_u$ be the number of hypercubes with basis $u$. Recall that $\sum_{u \in V} N_u \le 2^d n$. We begin with the definition of a DAG $H_u^L$ for hypercubes. It is called the *ladder Hasse diagram* of $u$. Its vertex set is made up of all pairs $(u, L)$ of hypercubes with basis $u$, in other words, $L$ is outgoing from $u$. There is an arc $(u, L') \to (u, L)$ if $L' \subseteq L$ and $|L'| = |L| - 1$. All diagrams $H_u^L$, $u \in V$, can be constructed in time $\tilde{O}(2^d n)$. Indeed, all hypercubes can be enumerated in $\tilde{O}(2^d n)$ with a BFS (Lemma 12). Then, it suffices, for each $(u, L)$, to consider the at most $d$ subsets $L' \subseteq L$ differing from one element from $L$ and connect $(u, L')$ to $(u, L)$. In this way, we obtain a directed graph where its connected components are the diagrams $H_u^L$. An example of DAG $H_u^L$ follows.

Thanks to the ladder Hasse diagram, computing a list of the MOPs in $\tilde{O}(2^d n)$ is straightforward as they are exactly the leaves of the DAGs $H_u^L$.
<figure><img src="image_18.png" /><figcaption>Fig. 15: Ladder Hasse diagram $H_u^L$</figcaption></figure>

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

**Computation of $\varphi$-labelings.** We present a new procedure to compute the labels $\varphi(u, L)$. A key distinction with the former method should be mentioned: instead of determining labels $\varphi(u, L)$ only, we also compute another type of labels, denoted by $\varphi\subseteq(u, L)$. These maximal ladder labels contain in fact the maximum over all labels $\varphi(u, L')$ such that $L' \subseteq L$. In brief, $\varphi\subseteq(u, L) = \max_{L'\subseteq L} \varphi(u, L')$.

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

$$ \varphi(u, L) = \max_{\substack{(u^+, L^+) \text{ MOP, } L \text{ incoming into } u \\ \forall E_j \in L_\perp^+, L \cup \{E_j\} \text{ not POF}}} (|L| + \varphi\subseteq(u^+, L_\perp^+)). \quad (8) $$

We explain why Equation (8) is correct. According to Equation (4), $\varphi(u, L)$ is $|L|$ plus the maximum over all $\varphi(u^+, L_\perp^+)$ - not necessarily MOPs - such that $L_\perp^+$ is $L$-parallel. Assume $(u^+, L_\perp^+)$ is not a MOP: there is a MOP $(u^+, L^+)$, where $L_\perp^+ \subseteq L^+$. As $L_\perp^+$ is the maximal $L$-parallel subset of $L^+$, we have $L_\perp^+ \subseteq L_\perp^+$. So, $\varphi(u^+, L_\perp^+) \le \varphi\subseteq(u^+, L_\perp^+)$ by definition. Conversely, value $\varphi\subseteq(u^+, L_\perp^+)$ counts in the computation of $\varphi(u, L)$ because all subsets of $L_\perp^+$ are $L$-parallel. Therefore, it suffices to consider the MOPs $(u^+, L^+)$ with their maximal subset $L_\perp^+$ instead of all hypercubes $(u^+, L_\perp^+)$.

Second, we explain how the labels $\varphi\subseteq$ are deduced from the values $\varphi(u, L)$. Assume that for a given vertex $u$, all $\varphi(u, L)$, $L$ outgoing from $u$, have been determined recursively, thanks to the base case or Equation (8). We deduce all $\varphi\subseteq(u, L)$ with the ladder Hasse diagram structure $H_u^L$. We proceed inductively. The base case
concerns singleton POFs: $\varphi(u, \{E_i\}) = \varphi_{\subseteq}(u, \{E_i\})$. Then, we describe the induction step. We modify the value $\varphi_{\subseteq}(u, L)$ by comparing $\varphi(u, L)$ with all $\varphi_{\subseteq}(u, L')$, where $L' \subseteq L$, $|L'| = |L|-1$. In other words, we initialize $\varphi_{\subseteq}(u, L)$ as $\varphi(u, L)$ and, for each arc $(u, L') \to (u, L)$ of $H_u^L$, we execute $\varphi_{\subseteq}(u, L) \leftarrow \max \varphi_{\subseteq}(u, L')$. Concretely, we transfer the $\varphi_{\subseteq}$-labelings from the roots to the leaves of the diagram $H_u^L$.

To compute labels $\varphi(u, L)$, the enumeration of MOPs is needed to apply Equation (8). For each MOP $(u^+, L^+)$, we have to consider all POFs $L$ incoming into $u$, which gives a total of at most $\tilde{O}(2^d f(d, n)n)$ triplets $(L, u^+, L^+)$, as the number of MOPs is $\tilde{O}(f(d, n)n)$. The logarithmic extra costs do not increase this runtime. To compute labels $\varphi_{\subseteq}(u, L)$, our induction is based on the structure of all diagrams $H_u^L$. The total size (number of arcs) of the DAG $H_u^L$ is $\tilde{O}(N_u)$ as each element has at most $d$ parents. Therefore, the execution time needed to determine all $\varphi_{\subseteq}(u, L)$ does not exceed $\tilde{O}(2^d n)$. In summary, the entire procedure to compute $\varphi, \varphi_{\subseteq}$-labelings is in $\tilde{O}(2^d f(d, n)n)$.

**Computation of op-labelings.** We already know that all labels $\text{op}_u(L)$ can be determined in time $\tilde{O}(2^d n)$, according to Theorem 7.

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

We define the *anti-ladder Hasse diagram* $H_u^{AL}$ of $u$. Its vertex set is made up of all pairs $(u, R)$ of hypercubes with anti-basis $u$ and a POF $R$ incoming into $u$. There is an arc $(u', R') \to (u, R)$ if both hypercubes (defined by their anti-basis and signature) have the same basis, $R' \supseteq R$ and $|R'| = |R| + 1$. As for diagrams $H_u^L$, all DAGs $H_u^{AL}$ can be constructed in time $\tilde{O}(2^d n)$ with a standard BFS.

As for $\varphi$-labelings, we define two label functions which will be computed jointly. However, the description is a bit trickier. We compute not only labels $\psi(u, R)$ but also the new ones $\psi_{\supseteq}(u, R)$. Contrary to $\varphi_{\subseteq}$-labelings, value $\psi_{\supseteq}(u, R)$ is not so easy to define. To understand, we recall the inductive process to compute labels $\psi(u, R)$ in Section 4.1.3.

Remember that there are two cases. Let $u^-$ be the basis of $(u, R)$. First, value $\psi(u, R)$ can be given by a distance $d(u, v)$ such that $m(u, v, v_0) = u^-$. In this case, $\psi(u, R) = |R| + \varphi(u^-, \text{op}_u^-(R))$. In the new procedure, we initialize all $\psi(u, R)$ with this value. Second, we may have $m(u, v, v_0) \neq u^-$. In this case, value $\psi(u, R)$ is given by the recursive formula in Equation (5). We can now define labels $\psi_{\supseteq}$. Let $R^-$ be a POF incoming into $u^-$ and assume that $(u^-, R)$ is a MOP. Let $R_\perp$ be the set containing exactly the $\Theta$-classes $E_i$ of $R$ such that $R$ is $R^-$-parallel. We denote by $u_\perp$ the anti-basis of the hypercube with basis $u^-$ and signature $R_\perp$. Then, value $|R| + \psi(u^-, R^-)$, which counts originally in the computation of $\psi(u, R)$ (Equation (5)), will count only for the computation of $\psi_{\supseteq}(u_\perp, R_\perp)$. More formally,

$$ \psi_{\supseteq}(u_\perp, R_\perp) = \max_{\substack{R^- \text{ POF incoming to } u^-, \\ \exists(u^-, R) \text{ MOP with } R_\perp \text{ max subset of } R \\ \text{such that } \forall E_j \in R_\perp, R^- \cup \{E_j\} \text{ not POF}}} (|R| + \psi(u^-, R^-)) \quad (9) $$

Observe that certain pairs $(u, R)$ may not admit a value $\psi_{\supseteq}(u, R)$ according to this definition. In this case, we simply fix $\psi_{\supseteq}(u, R) = 0$.

Now, we show that value $\psi(u, R)$, in the case $m \neq u^-$, is exactly the maximum over all $\psi_{\supseteq}(u', R')$ such that both hypercubes (defined by anti-basis and signature)
have the same basis and $R \subseteq R'$. On one hand, if $(u^-, R)$ is not a MOP, there is a MOP $(u^-, R^*)$, where $R \subsetneq R^*$. Let $R^-$ be a POF incoming into $u^-$ such that $R$ is $R^-$-parallel. Let $R_\perp^*$ be the maximal $R^-$-parallel subset of $R^*$. Set $R_\perp^*$ is a POF and $R \subseteq R_\perp^*$ by definition. Assume $\psi(u, R) = |R| + \psi(u^-, R^-)$: this value is counted in $\psi_\perp(u^-, R_\perp^*)$ but not in $\psi_\perp(u, R)$ if $R \neq R_\perp^*$. On the other hand, if some $R' \supseteq R$ is $R^-$-parallel, then $R$ also does. So, we have:

$$ \psi(u, R) = \max \left\{ |R| + \varphi(u^-, \mathbf{op}_{u^-(R)}), \max_{\substack{R \subseteq R' \\ (u', R') \text{ same basis as } (u, R)}} \psi_\perp(u', R') \right\}. \quad (10) $$

Given a basis $u^-$, we compute all nonnegative values $\psi_\perp(u, R)$ such that $u^-$ is the basis of the hypercube with anti-basis $u$ and signature $R$. To do so, we enumerate all triplets $(R^-, u^-, R)$ such that $R^-$ is incoming into $u^-$ and $(u^-, R)$ is a MOP. We compute the maximal $R^-$-parallel subset $R_\perp$ of $R$ and apply Equation (9). As for $\varphi$-labelings, it consist in an enumeration scheme in $\tilde{O}(2^d f(d, n)n)$.

Then, we deduce labels $\psi(u, R)$ of the hypercubes with basis $u^-$. We use the anti-ladder Hasse diagram $H_u^{AL}$. If $(u^-, R)$ is a MOP, then $(u, R)$ is a root of $H_u^{AL}$, and we fix $\psi(u, R)$ as the maximum between its initial value (case $m(u, v, v_0) = u^-$) and $\psi_\perp(u, R)$: it corresponds to Equation (10) when $R$ is maximal. Otherwise, $\psi(u, R)$ can be computed from Equation (10) in function of $\psi_\perp(u', R')$ where $(u', R')$ is a parent of $(u, R)$ in $H_u^{AL}$. The time cost of this step is at most $\tilde{O}(2^d n)$, due to the size of DAG $H_u^{AL}$. In summary, we obtain the same global running time than for labels $\varphi(u, L)$, which is $\tilde{O}(2^d f(d, n)n)$. $\square$

### 5.2.2 Cardinality of MOPs

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

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

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

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

*Proof* Let $u^+$ be the anti-basis of $(u, L)$. Assume, by way of contradiction, that $L^*$ is not maximal. There is a $\Theta$-class $E_h$ such that $L^{**} = L^* \cup \{E_h\}$ is a POF. Let $u'$ be the vertex such that $\mathcal{E}^-(u') = L^{**}$.
48

Subquadratic-time algorithm for the diameter on median graphs

For every $E_i \in L^*$, vertices $u^+$ and $u'$ belongs to $\partial H_i''$. The intersection of these boundaries, that we denote by $\partial H^*$, is convex. Therefore, all vertices metrically between $u^+$ and $u'$ belong to $\partial H^*$. For this reason, there is necessarily an edge $e$ incident to $u^+$ whose second endpoint is also in $\partial H^*$. Let $e = (u^+, w)$ be this edge and we denote by $E_j$ its $\Theta$-class. If $e$ is incoming into $u^+$ with the $v_0$-orientation, then we have a contradiction, since $p(u, L) = (L, L^*) \neq (L, L^{**})$. We know that $e$ is outgoing from $u^+$. Recall that $E_j$ is orthogonal to any $\Theta$-class of $L^*$. By successive applications of Lemma 8, we show that for any vertex of the hypercube of anti-basis $u^+$ and signature $L^*$, among them $u$, there is an edge of $E_j$ outgoing from it. Here comes the contradiction: $L$ is not a maximal POF outgoing from $u$ as $L \cup \{E_j\}$ is a POF ($L \subseteq L^*$). $\square$

Maximal POFs can be interpreted in the crossing graph $G^\#$ (Definition 6). As it describes the orthogonality of $\Theta$-classes, a POF of $G$ is exactly a clique of $G^\#$. Naturally, a maximal POF corresponds to a maximal clique of $G^\#$. We provide an upper bound of the number of MOPs of $G$ which depends on the maximal cliques of its crossing graph.

**Corollary 3 (MOPs as subsets of maximal cliques in $G^\#$)** Let $G^\#$ be the crossing graph of $G$ and $C_{max}^\#$ be the set of maximal cliques of $G^\#$. The number of MOPs in $G$ is at most $\sum_{C \in C_{max}^\#} 2^{|C|}$.

*Proof* We begin with the proof that application $p$ is injective. Let us consider a pair $(L, L^*) = p(u, L)$. There is a unique vertex $u^+$ such that $\mathcal{E}^- = L^*$. Necessarily, if $(u, L) = p^{-1}(L, L^*)$, then vertex $u$ is the basis of the hypercube with signature $L$ and anti-basis $u^+$, which is unique.

Now, application $p$ is restricted to MOPs only. We know it is injective and that, for any MOP $(u, L)$, set $L^*$ of $p(u, L) = (L, L^*)$ is a maximal POF. Concretely, the number of MOPs is at most the following value: for each maximal POF, add the number of its nonempty subsets (which is 2 to the power its cardinality minus 1).

We remind the reader that a POF of $G$ corresponds to an induced clique of its crossing graph $G^\#$. Naturally, a maximal clique of $G^\#$ represents a maximal POF. It follows that the number of MOPs of $G$ is at most $\sum_{C \in C_{max}^\#} (2^{|C|-1}) \le \sum_{C \in C_{max}^\#} 2^{|C|}$. $\square$

We define a parameter, the *maximal clique ratio*. Its role is to provide an upper bound of the ratio between the number of MOPs of a median graph and the number of vertices $n$.

**Definition 20 (Maximal clique ratio)** The maximal clique ratio $r(H)$ of a graph $H$ is the quotient between the sum of the number of subsets of each maximal clique of $H$ by the number of cliques of $H$. Formally,

$$r(H) = \frac{\sum_{C \in C_{max}(H)} 2^C}{\frac{R[H]}{N[H]}} = \frac{\sum_{C \in C_{max}(H)} 2^C}{|C(H)|}$$
Observe that, for $H = G^\#$, $N[H] = |V(G)| = n$. The clique number of a graph is the size of its maximum clique. The dimension $d$ of $G$ is also the clique number of $G^\#$. Complete multipartite graphs (with clique number $d$) are the graphs whose vertex set can be partitioned into independent sets $A_i$, $1 \le i \le d$, and any pair of vertices belonging to a different set form an edge.

We begin with the proof that the complete multipartite graphs maximize the ratio $r(H)$. Next, we show that the more the complete multipartite graph is balanced, the larger $r(H)$ is.

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

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

*Proof* If $H$ is not complete multipartite, there is a pair $u, v$ of vertices such that $(u, v) \notin E$ and $N(u) \neq N(v)$. Let $N_u$ (resp. $N_v$) be the number of cliques of $H$ containing $u$ (resp. $v$). For $x \in \{u, v\}$, we denote by $R_x$ the following value: $R_x = \sum_{C \in \mathcal{C}_{\max(H)}} 2^{|C|}$. For the remainder, we fix $\Delta R = R_v - R_u$ and $\Delta N = N_v - N_u$. We

define two graphs $H_{u \to v}$ and $H_{v \to u}$, and compare their maximal clique ratio with the initial graph $H$.

Graph $H_{u \to v}$ is obtained from $H$ by removing $u$ and adding a copy $v'$ of $v$ such that $N(v') = N(v)$. We have $r(H_{u \to v}) = \frac{R[H] + \Delta R}{N[H] + \Delta N}$, as $u$ and $v$ cannot belong to the same clique. Conversely, graph $H_{v \to u}$ is obtained from $H$ by removing $v$ and adding a copy $u'$ of $u$ such that $N(u') = N(u)$. We have $r(H_{v \to u}) = \frac{R[H] - \Delta R}{N[H] - \Delta N}$. Both $H_{u \to v}$ and $H_{v \to u}$ do not increase the clique number of $H$. One can check that if $\frac{R[H] + \Delta R}{N[H] + \Delta N} \le \frac{R[H]}{N[H]}$, then $\frac{R[H] - \Delta R}{N[H] - \Delta N} \ge \frac{R[H]}{N[H]}$ and vice-versa. If the inequality is strict, then we have a contradiction since $H$ is supposed to maximize $r(H)$ for graphs with $q$ vertices and clique number at most $d$. The only possibility we have is $r(H) = r(H_{u \to v}) = r(H_{v \to u})$.

We prove that either $H_{u \to v}$ or $H_{v \to u}$ has less triplets with only two adjacent vertices than $H$. Let $\text{Trp}_u$ (resp. $\text{Trp}_v$) be the number of triplets of $H$ containing $u$ and not $v$ (resp. $v$ and not $u$). Let $\text{Trp}_{u/v}$ (resp. $\text{Trp}_{v/u}$) the number of triplets of $H$ containing both $u$ and $v$, where $u$ is the isolated vertex (resp. $v$ is the isolated vertex). We have

$$ \text{Trp}(H_{u \to v}) = \text{Trp}(H) + \text{Trp}_v - \text{Trp}_u - \text{Trp}_{u/v} - \text{Trp}_{v/u}, $$

$$ \text{Trp}(H_{v \to u}) = \text{Trp}(H) + \text{Trp}_u - \text{Trp}_v - \text{Trp}_{u/v} - \text{Trp}_{v/u}. $$
50

Subquadratic-time algorithm for the diameter on median graphs

At least one of these values is smaller than Trp(H), otherwise Trp<sub>u/v</sub> = Trp<sub>v/u</sub> = 0,
which is equivalent to saying N(u) = N(v), a contradiction.
□

By successive applications of this result, for any graph *H* of clique number at most *d* maximizing *r*(*H*), there exists a complete multipartite graph *H'* with the same ratio and clique number at most *d*. Turán graphs *T*(*q*, *d*) are the most balanced complete multipartite graphs with *q* vertices and clique number *d*. The sizes of two of its independent sets differ by at most one. Now, the objective is to prove that, among complete multipartite graphs, Turán graphs maximize the maximal clique ratio.

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

*Proof* We consider a complete multipartite graph *H* with *q* vertices and clique number *d*. The vertex set of *H* can be partitioned into *d* independent sets *A*ᵢ: *V*(*H*) = ⋃₁<sup>*d*</sup> *A*ᵢ. Let *α*ᵢ = |*A*ᵢ|. Assume, w.l.o.g, that the sizes of sets *A*ᵢ are increasing, i.e. *α*₁ ≤ *α*₂ ≤ ... ≤ *α*ₐ. Recall that ∑₁<sup>*d*</sup> *α*ᵢ = *q*. Turán graphs are the graphs such that *α*<sub>*d*</sub> − *α*₁ ≤ 1.

Assume that, on graph $H$, $\alpha_d - \alpha_1 \ge 2$. We prove adding a vertex to $A_1$ and removing another one from $A_d$ increases the maximal clique ratio, without changing $q$ or $d$. Let $H'$ denote the graph after this transformation. All maximal cliques in $H$ have size $d$, so $R[H] = 2^d \prod_1^d \alpha_i$. The number $N[H]$ of (not necessarily maximal) cliques of $H$ is expressed as: $N[H] = \sum_{J \subseteq \{1, \dots, d\}} \prod_{j \in J} \alpha_j$. Values $R[H']$ and $N[H']$

can be deduced by replacing respectively $\alpha_1$ and $\alpha_d$ by $\alpha_1 + 1$ and $\alpha_d - 1$. We assess
the quotient between $r(H')$ and $r(H)$. Certain details of our calculations are omitted
to keep the paper readable, we restrict ourselves to the main steps of the reasoning.

$$
\frac{r(H')}{r(H)} = \frac{\frac{R[H']}{R[H]}}{\frac{N[H']}{N[H]}} = \frac{\frac{\alpha_1+1}{\alpha_1} \frac{\alpha_d-1}{\alpha_d}}{1 + \frac{\alpha_d-\alpha_1-1}{(\alpha_1+1)(\alpha_d+1)}} = \left(1 + \frac{1}{\alpha_1(\alpha_1+2)}\right) \left(1 - \frac{1}{\alpha_d^2}\right) > 1.
$$

Indeed, as $\alpha_d - \alpha_1 \ge 2$, one can check that $(1 + \frac{1}{\alpha_1(\alpha_1+2)}) (1 - \frac{1}{(\alpha_1+2)^2})$ is greater
than 1 for any value of $\alpha_1$.
□

Naturally, we use the maximal clique ratio of Turán graphs to deduce an
upper bound for the number of MOPs of any median graph G.

**Corollary 4** The number of MOPs in a median graph is $O(f(d,n)n)$, where
$f(d,n) = \left(2^{\frac{\log n}{d}} - 1\right)^d$.

*Proof* According to Corollary 3, the number of MOPs of a median graph *G* is upper-
bounded by *r*(*G*<sup>#</sup>)*n*. Furthermore, Theorem **15** states that the balanced complete
multipartite graphs maximize $r(H)$. Hence,

$$r(G^{\#}) \le \frac{2^d \binom{q}{d}^d}{\sum_{j=1}^d \binom{d}{j} \binom{q}{d}^j} \le \frac{2^d \binom{q}{d}^d}{(1+q)^d} \quad (11)$$

The number of cliques of $G^{\#}$ is exactly the number of POFs of $G$. Therefore, $n = |V(G)| = (1+q/d)^d$. We fix $a = d/\log n$, we have $0 < a \le 1$. We obtain that $2^a = (1+q/d)^d$ and, thus, $q/d = 2^{1/a} - 1$. Finally, we inject this equality into Equation (11). □

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

**Theorem 16** There is a combinatorial algorithm determining all eccentricities in $\tilde{O}(n^{1.6456})$.

*Proof* Let $a = d/\log n$ and we define two functions: $f(x) = 2^{\frac{1}{2x}-1}$ and $g(x) = 2 - \frac{1}{1+\log(2f(x))}$. □

One one hand, according to Theorem 9, there is a combinatorial algorithm determining all eccentricities in $\tilde{O}(2^{2d}n) = \tilde{O}(n^{1+2a})$.

On the other hand, according to Theorem 13 and Corollary 4, we can compute all labels $\phi$, op and $\psi$ in time $\tilde{O}(2^d(f(a))^d n)$. Using the reduction scheme of Theorem 25, we can compute all eccentricities in time $\tilde{O}(n^{g(a)})$.

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

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

# 6 Conclusion

As a natural extension of this work, the question of designing a linear-time or quasilinear-time algorithm to compute the diameter and all eccentricities of median graphs is now open. With the recursive splitting procedure of Lemma 25, unfortunately, the best execution time we could obtain at best is $\tilde{O}(n^{3/2})$. Reaching this bound could represent a first reasonable objective: it
would “suffice” to propose a FPT combinatorial algorithm which computes all labels in $\tilde{O}(2^d n)$ in order to obtain such time complexity. We see the MOP-approach as a gateway to identify such a procedure.

Another - certainly easier - objective after this work is to adapt the recursive splitting of Lemma 25 for reach centralities. We tried to define a weighted version of the reach centralities problem in order to fit them to the halfspace separation, but this task seems to be not so easy. Our hope is to obtain a subquadratic-time algorithm computing reach centralities in median graphs.

Eventually, we note two lines of research on which this paper could have some influence: (i) the study of efficient algorithms for the computation of other metric parameters on median graphs (perhaps, the *betweenness centrality* [39]) and (ii) the design of subquadratic-time algorithms for the diameter and all eccentricities on larger families of graphs (*almost-median* or *semi-median* graphs [40, 41] for example). Concerning the betweenness centrality, our intuition is that the labeling framework introduced [26] does not suffice to describe the number of $(u, v)$-paths passing through some vertex, which is exactly what betweenness centrality assesses.

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

## References

[1] Avann, S.P.: Metric ternary distributive semi-lattices. Proc. Amer. Math. Soc. **12**, 407–414 (1961)

[2] Birkhoff, G., Kiss, S.A.: A ternary operation in distributive lattices. Bull. Amer. Math. Soc. **53**, 745–752 (1947)

[3] Bandelt, H., Chepoi, V.: Metric graph theory and geometry: a survey. Contemp. Math. **453**, 49–86 (2008)

[4] Chepoi, V.: Graphs of some CAT(0) complexes. Adv. Appl. Math. **24**(2), 125–179 (2000)

[5] Barthélemy, J., Constantin, J.: Median graphs, parallelism and posets. Discret. Math. **111**(1-3), 49–63 (1993)

[6] Sassone, V., Nielsen, M., Winskel, G.: A classification of models for concurrency. In: Proc. of CONCUR. Lecture Notes in Computer Science, vol. 715, pp. 82–96 (1993)

[7] Bandelt, H., Quintana-Murci, L., Salas, A., Macaulay, V.: The fingerprint of phantom mutations in mitochondrial dna data. Am. J. Hum. Genet. **71**, 1150–1160 (2002)
[8] Bandelt, H.J., Forster, P., Sykes, B.C., Richards, M.B.: Mitochondrial portraits of human populations using median networks. Genetics **141**(2), 743–753 (1995)

[9] Abboud, A., Williams, V.V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: Proc. of SODA, pp. 377–391 (2016)

[10] Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. In: Proc. of SODA, pp. 2143–2152 (2017)

[11] Ducoffe, G., Habib, M., Viennot, L.: Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension. SIAM J. Comput. **51**(5), 1506–1534 (2022). https://doi.org/10.1137/20m136551x

[12] Chechik, S., Larkin, D.H., Roditty, L., Schoenebeck, G., Tarjan, R.E., Williams, V.V.: Better approximation algorithms for the graph diameter. In: Proc. of SODA, pp. 1041–1052 (2014)

[13] Roditty, L., Williams, V.V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proc. of STOC, pp. 515–524 (2013)

[14] Mulder, M.: The structure of median graphs. Discret. Math. **24**(2), 197–204 (1978)

[15] Mulder, M.: The interval function of a graph. Mathematical Centre Tracts, Mathematisch Centrum, Amsterdam (1980)

[16] Bandelt, H.: Retracts of hypercubes. Journal of Graph Theory **8**(4), 501–510 (1984)

[17] Mulder, H.M., Schrijver, A.: Median graphs and Helly hypergraphs. Discret. Math. **25**(1), 41–50 (1979)

[18] Klavzar, S., Mulder, H.M., Skrekovski, R.: An Euler-type formula for median graphs. Discret. Math. **187**(1-3), 255–258 (1998)

[19] Bénéteau, L., Chalopin, J., Chepoi, V., Vaxès, Y.: Medians in median graphs and their cube complexes in linear time. In: Proc. of ICALP, vol. 168, pp. 10–11017 (2020)

[20] Hagauer, J., Imrich, W., Klavzar, S.: Recognizing median graphs in subquadratic time. Theor. Comput. Sci. **215**(1-2), 123–136 (1999)

[21] Imrich, W., Klavzar, S., Mulder, H.M.: Median graphs and triangle-free
54 *Subquadratic-time algorithm for the diameter on median graphs*
graphs. SIAM J. Discret. Math. **12**(1), 111–118 (1999)

[22] Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica **17**(3), 209–223 (1997)

[23] Chepoi, V., Dragan, F.F., Vaxès, Y.: Center and diameter problems in plane triangulations and quadrangulations. In: Proc. of SODA, pp. 346–355 (2002)

[24] Ducoffe, G.: Isometric embeddings in trees and their use in distance problems. In: Proc. of MFCS. LIPIcs, vol. 202, pp. 43–14316 (2021)

[25] Chepoi, V., Labourel, A., Ratel, S.: Distance labeling schemes for cube-free median graphs. In: Proc. of MFCS, vol. 138, pp. 15–11514 (2019)

[26] Bergé, P., Habib, M.: Diameter, radius and all eccentricities in linear time for constant-dimension median graphs. In: Proc. of LAGOS (2021)

[27] Barthélemy, J., Leclerc, B., Monjardet, B.: On the use of ordered sets in problems of comparison and consensus of classifications. Journal of Classification **3**, 187–224 (1986)

[28] Gutman, R.J.: Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In: Proc. of ALENEX/ANALC, pp. 100–111 (2004)

[29] Bandelt, H., Chepoi, V., Eppstein, D.: Combinatorics and geometry of finite and infinite squaregraphs. SIAM J. Discret. Math. **24**(4), 1399–1440 (2010)

[30] Hammack, R., Imrich, W., Klavžar, S.: Handbook of Product Graphs. CRC press, Boca Raton, FL (2011)

[31] Kovse, M.: Complexity of phylogenetic networks: counting cubes in median graphs and related problems. Analysis of complex networks: From Biology to Linguistics, 323–350 (2009)

[32] McMorris, F.R., Mulder, H.M., Roberts, F.S.: The median procedure on median graphs. Discret. Appl. Math. **84**(1-3), 165–181 (1998)

[33] Bandelt, H., Chepoi, V., Dress, A.W.M., Koolen, J.H.: Combinatorics of lopsided sets. Eur. J. Comb. **27**(5), 669–689 (2006)

[34] Bandelt, H., van de Vel, M.: Embedding topological median algebras in products of dendrons. Proc. London Math. Soc. **58**, 439–453 (1989)

[35] Klavzar, S., Mulder, H.M.: Partial cubes and crossing graphs. SIAM J. Discret. Math. **15**(2), 235–251 (2002)
[36] Habib, M., Paul, C., Viennot, L.: Partition refinement techniques: An interesting algorithmic tool kit. Int. J. Found. Comput. Sci. **10**(2), 147–170 (1999)

[37] Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. **16**(6), 973–989 (1987)

[38] Winkler, P.M.: Isometric embedding in products of complete graphs. Discrete Applied Mathematics **7**(2), 221–225 (1984)

[39] Abboud, A., Grandoni, F., Williams, V.V.: Subcubic equivalences between graph centrality problems, APSP and diameter. In: Proc. of SODA, pp. 1681–1697 (2015)

[40] Bresar, B.: Characterizing almost-median graphs. Eur. J. Comb. **28**(3), 916–920 (2007)

[41] Klavzar, S., Shpectorov, S.V.: Characterizing almost-median graphs II. Discret. Math. **312**(2), 462–464 (2012)