Medians in median graphs in linear time
share
The median of a graph G is the set of all vertices x of G minimizing the sum of distances from x to all other vertices of G. It is known that computing the median of dense graphs in subcubic time refutes the APSP conjecture and computing the median of sparse graphs in subquadratic time refutes the HS conjecture. In this paper, we present a linear time algorithm for computing medians of median graphs, improving over the existing quadratic time algorithm. Median graphs constitute the principal class of graphs investigated in metric graph theory, due to their bijections with other discrete and geometric structures (CAT(0) cube complexes, domains of event structures, and solution sets of 2-SAT formulas). Our algorithm is based on the known majority rule characterization of medians in a median graph G and on a fast computation of parallelism classes of edges (Θ-classes) of G. The main technical contribution of the paper is a linear time algorithm for computing the Θ-classes of a median graph G using Lexicographic Breadth First Search (LexBFS). Namely, we show that any LexBFS ordering of the vertices of a median graph G has the following fellow traveler property: the fathers of any two adjacent vertices of G are also adjacent. Using the fast computation of the Θ-classes of a median graph G, we also compute the Wiener index (total distance) of G in linear time.
READ FULL TEXT