Linear-time graph distance and diameter approximation

In this study, we consider the problem of estimating the diameter of a graph, that is, the maximum distance between any two vertices, in linear time. We address a question posed in the literature–whether there exists an interesting graph class with arbitrarily large cycles for which breadth first search (BFS) would always return high‐eccentricity vertices. We answer this question positively, defining a class of graphs that generalizes AT‐free graphs and has no bound on the size of induced cycles, yet BFS always returns a vertex whose eccentricity is within a constant difference from the diameter. In addition, we consider the question–also explicitly stated in the literature–whether some variant of the so‐called multisweep algorithm would always return a high‐eccentricity vertex. We show that the answer is negative by describing a family of graphs for which no variant of multisweep BFS can return a vertex of eccentricity higher than half of the diameter plus a constant.