${\alpha }_i$-Metric Graphs: Radius, Diameter and all Eccentricities

Abstract

We extend known results on chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph is called ${\alpha }_i$-metric ($i\in \mathcal{N}$) if it satisfies the following ${\alpha }_i$-metric property for every vertices $u,w,v$ and $x$: if a shortest path between $u$ and $w$ and a shortest path between $x$ and $v$ share a terminal edge $vw$, then $d(u,x)\ge d(u,v)+d(v,x)-i$. Roughly, gluing together any two shortest paths along a common terminal edge may not necessarily result in a shortest path but yields a ``near-shortest'' path with defect at most $i$. It is known that ${\alpha }_0$-metric graphs are exactly ptolemaic graphs, and that chordal graphs and distance-hereditary graphs are ${\alpha }_i$-metric for $i=1$ and $i=2$, respectively. We show that an additive $O(i)$-approximation of the radius, of the diameter, and in fact of all vertex eccentricities of an ${\alpha }_i$-metric graph can be computed in total linear time. Our strongest results are obtained for ${\alpha }_1$-metric graphs, for which we prove that a central vertex can be computed in subquadratic time, and even better in linear time for so-called $({\alpha }_1,\Delta )$-metric graphs (a superclass of chordal graphs and of plane triangulations with inner vertices of degree at least $7$). The latter answers a question raised in (Dragan, IPL, 2020). Our algorithms follow from new results on centers and metric intervals of ${\alpha }_i$-metric graphs. In particular, we prove that the diameter of the center is at most $3i+2$ (at most $3$, if $i=1$). The latter partly answers a question raised in (Yushmanov & Chepoi, Mathematical Problems in Cybernetics, 1991).

To appear in WG'23