A story of diameter, radius and Helly property
share
A graph is Helly if every family of pairwise intersecting balls has a nonempty common intersection. Motivated by previous work on dually chordal graphs and graphs of bounded distance VC-dimension (with the former being a subclass of Helly graphs and the latter being a particular case of graphs of bounded fractional Helly number, respectively) we prove several new results on the complexity of computing the diameter and the radius on Helly graphs and related graph classes. * First, we present an algorithm which given an n-vertex m-edge Helly graph G as input, computes w.h.p. rad(G) in time Õ(m√(n)). Incidentally, it also gives us an additive +1-approximation of diam(G). * Then, we focus on C_4-free Helly graphs, which include, amongst other subclasses, bridged Helly graphs and so, chordal Helly graphs and hereditary Helly graphs. For the C_4-free Helly graphs, we present linear-time algorithms for computing the eccentricity of all vertices. Doing so, we generalize previous results on strongly chordal graphs to a much larger subclass. * Finally, we derive from our findings on chordal Helly graphs a more general one-to-many reduction from diameter computation on chordal graphs to either diameter computation on split graphs or the Disjoint Set problem. Therefore, split graphs are in some sense the only hard instances for diameter computation on chordal graphs. As a byproduct of our reduction we get that on any subclass of chordal graphs with constant VC-dimension the diameter can be computed in truly subquadratic time. These above results are a new step toward better understanding the role of abstract geometric properties in the fast computation of metric graph invariants.
READ FULL TEXT