Authors: David Coudert ¹; Samuel Coulomb ²; Guillaume Ducoffe ^3,4

• 1 Combinatorics, Optimization and Algorithms for Telecommunications
• 2 École normale supérieure - Paris
• 3 University of Bucharest
• 4 National Institute for Research and Development in Informatics [Bucharest]

Let u and v be vertices in a connected graph G = (V, E). For any integer k such that 0 ≤ k ≤ dG (u, v), the k-slice Sk (u, v) contains all vertices x on a shortest uv-path such that dG (u, x) = k. The leanness of G is the maximum diameter of a slice. This metric graph invariant has been studied under different names, such as "interval thinness" and "fellow traveler property". Graphs with leanness equal to 0, a.k.a. geodetic graphs, also have received special attention in Graph Theory. The practical computation of leanness in real-life complex networks has been studied recently (Mohammed et al., COMPLEX NETWORKS'21). In this paper, we give a finer-grained complexity analysis of two related problems, namely: deciding whether the leanness of a graph G is at most some small value ℓ; and computing the leanness on specific graph classes. We obtain improved algorithms in some cases, and time complexity lower bounds under plausible hypotheses.

• 05C10 - Planar graphs; geometric and topological aspects of graph theory
• 05C82 - Small world graphs, complex networks (graph-theoretic aspects)
• 05C85 - Graph algorithms (graph-theoretic aspects)