Quasilinear-time eccentricities computation, and more, on median graphs

Computing the diameter, and more generally, all eccentricities of an undirected graph is an important problem in algorithmic graph theory and the challenge is to identify graph classes for which their computation can be achieved in subquadratic time. Using a new recursive scheme based on the structural properties of median graphs, we provide a quasilinear-time algorithm to determine all eccentricities for this well-known family of graphs. Our recursive technique manages specifically balanced and unbalanced parts of the Θ-class decomposition of median graphs. The exact running time of our algorithm is O(n log 4 n). This outcome not only answers a question asked by Bénéteau et al. (2020) but also greatly improves a recent result which presents a combinatorial algorithm running in time O(n 1.6408 log O(1) n) for the same problem.

Furthermore we also propose a distance oracle for median graphs with both polylogarithmic size and query time. Speaking formally, we provide a combinatorial algorithm which computes for any median graph G, in quasilinear time O(n log 4 (n)), vertex-labels of size O(log 3 (n)) such that any distance of G can be retrieved in time O(log 4 (n)) thanks to these labels.

closest-to-u vertex on the other side (its gate), the distance to its gate, and finally the label of u in the graph induced by its side regarding the balanced Θ-class. This whole package allows us to retrieve any distance between two vertices in poly-logarithmic time.

The unbalanced case requires more effort. Our idea consists in partitioning all vertices of the graph in function of their "direction" regarding the central vertex v 0 . To do so, we launch a BFS from v 0 and take note of some information, that will be added to the label of any vertex u = v 0 : the distance from v 0 to u, the Θ-classes traversed to go from v 0 to u, etc. In addition, some gates of u through certain small convex sets are also computed. With this information, we show again how to retrieve any distance in poly-logarithmic time.

Perspectives. First, we believe that the techniques proposed in this article offer not only tools for different problems on median graphs but also for more general classes of graphs. Observe that larger families of graphs are still impacted by the notion of Θ-class, the main difference consisting in weaker convex characterizations: almost median graphs [17], pseudomedian graphs [10,39] or partial cubes [40]. In our work, we exploit several times the fact that the boundary of each Θ-class is convex, which is a property specific to median graphs and not to these superclasses. Therefore, one should be able to get rid of this argument in order to handle larger families of graphs. However, a tradeoff on the balance of Θ-class stays, in our opinion, a promising starting point for tackling them.

Coming back to median graphs, one can hope producing efficient algorithms by exploiting again this tradeoff technique. A future direction of research could be trying to design algorithms which improve the naive general method for computing other metric parameters, such as the hyperbolicity [27], the betweenness and reach centralities [1],. . . The techniques proposed in our paper can be useful tools for such problems. Eventually, we mention a problem which was not studied yet on median graphs to the best of our knowledge: Weighted Center [13]. Given a median graph G with vertex weights ω : V → N, the objective is to determine the weighted center of (G, ω), i.e. the vertex u which minimizes max v∈V (G) ω(v)d(u, v). Observe that, with Theorem 1, we can deduce, from the weighted eccentricities, some kind of weighted center where weights stand as an additive term and not multiplicative. For this reason, we believe that the techniques we proposed can be fruitful for solving Weighted Center in quasilinear time. Note that Weighted Center admits exact quasilinear-time algorithms for trees and cactii [13], hence targeting median graphs is a natural challenge.