A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs

Guillaume Ducoffe

Authors on Pith no claims yet

Pith reviewed 2026-05-09 13:42 UTC · model grok-4.3

classification 💻 cs.DS cs.CC

keywords graphshyperbolicvertexcentralalgorithmgraphcenterdistance

0 comments

The pith

Linear-time algorithm for the center problem on 1/2-hyperbolic graphs, with a conditional lower bound ruling it out for 1-hyperbolic graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Gromov hyperbolicity measures how tree-like a graph's distance structure is. The center problem asks for a vertex whose farthest distance to any other vertex is as small as possible. For exact trees (hyperbolicity zero) this is solvable in linear time. Prior work gave a fast approximation for any fixed hyperbolicity but left the exact problem open beyond zero. This paper shows an exact linear-time algorithm still works up to hyperbolicity 1/2. It then proves that at hyperbolicity 1 the problem becomes hard for linear time, assuming the Hitting Set Conjecture. The threshold at 1/2 is therefore sharp.

Core claim

Our main contribution in the paper is a linear-time algorithm for computing a central vertex in the class of 1/2-hyperbolic graphs. Furthermore, we rule out the existence of such an algorithm for 1-hyperbolic graphs, under the Hitting Set Conjecture.

Load-bearing premise

The Hitting Set Conjecture holds, which is invoked to establish the conditional lower bound ruling out linear-time algorithms for 1-hyperbolic graphs.

read the original abstract

A vertex in a graph is called central if it minimizes its maximum distance to the other vertices. The radius of a graph $G$ is the largest distance between a central vertex and the other vertices, and it is denoted by $rad(G)$. In the center problem, we are asked to find a central vertex. We study the fine-grained complexity of the center problem on graphs with small Gromov hyperbolicity. Roughly, the Gromov hyperbolicity of a graph represents how close, locally, it is to a tree, from a metric point of view. It has applications in the design of approximation algorithms. In particular, there is a linear-time algorithm that for every $\delta$-hyperbolic graph $G$ outputs some vertex at distance at most $rad(G) + 5\delta$ to the other vertices [Chepoi et al, SoCG'08]. However, a linear-time algorithm for computing a central vertex is known only for $0$-hyperbolic graphs, whereas its existence was ruled out for $2$-hyperbolic graphs under the Hitting Set Conjecture of [Abboud et al, SODA'16]. Our main contribution in the paper is a linear-time algorithm for computing a central vertex in the class of $\frac 1 2$-hyperbolic graphs. Furthermore, we rule out the existence of such an algorithm for $1$-hyperbolic graphs, under the Hitting Set Conjecture, thus completely settling all the cases left open.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Ducoffe closes the remaining cases in the fine-grained complexity of the center problem for low-hyperbolicity graphs.

read the letter

This paper completes the fine-grained complexity classification for the center problem on δ-hyperbolic graphs. It introduces a linear-time algorithm for finding a central vertex when the graph is exactly 1/2-hyperbolic and proves a conditional lower bound ruling out linear time for 1-hyperbolic graphs, assuming the Hitting Set Conjecture. That fills the gap between the known linear-time result for 0-hyperbolic graphs and the existing conditional hardness for 2-hyperbolic graphs. The new algorithm builds directly on the known linear-time 5δ-approximation from Chepoi et al., refining it to exact for the 1/2 case by exploiting tighter structural properties of such graphs. The hardness result adapts the reduction technique from the 2-hyperbolic case to the 1 case. Both contributions are presented as settling the remaining open questions in the dichotomy. The work is solid in how it connects to prior results without introducing new conjectures beyond the standard one. The positive result is unconditional, which strengthens it. A minor soft spot could be that the exact threshold at 1/2 might require careful verification in the proofs to ensure no overlap or gap with the 1 case, but the abstract suggests the separation is clean. No issues with circular reasoning or unsupported claims at the high level. This is relevant for specialists in fine-grained algorithms on graphs with bounded hyperbolicity, particularly those studying distance problems and their complexity. Readers who have followed the line of work on centers in hyperbolic graphs will appreciate how it ties everything together. It is worth sending for peer review because it resolves the open cases with a combination of algorithmic and hardness results grounded in existing techniques.

Referee Report

0 major / 3 minor

Summary. The paper establishes a fine-grained dichotomy for the center problem on Gromov hyperbolic graphs. It gives a linear-time algorithm to compute a central vertex (one minimizing eccentricity) in 1/2-hyperbolic graphs, building on the known 5δ-approximation of Chepoi et al. (SoCG'08). It also proves that no linear-time algorithm exists for 1-hyperbolic graphs, assuming the Hitting Set Conjecture of Abboud et al. (SODA'16). This closes the gap between the known linear-time result for 0-hyperbolic graphs (trees) and the conditional hardness for 2-hyperbolic graphs.

Significance. If the claims hold, the result is significant: it supplies the missing cases that complete a clean complexity threshold at δ = 1/2 versus δ = 1 for exact linear-time solvability of the center problem. The positive result strengthens the existing approximation toolkit for hyperbolic metrics, while the negative result uses a standard, well-studied conjecture to obtain a tight separation. The work therefore gives a precise characterization of when the center problem becomes tractable in the hyperbolic regime.

minor comments (3)

The abstract and introduction should explicitly state the precise running time of the new algorithm (e.g., O(n) or O(n log n)) and the model of computation assumed for the linear-time claim.
Section 3 (or wherever the algorithm is presented) should include a short pseudocode block or high-level description of the key steps that achieve exact optimality for δ = 1/2, to make the improvement over the 5δ-approximation transparent.
The reduction for the conditional lower bound (presumably in Section 4) should clarify whether the constructed 1-hyperbolic graphs remain simple or require multiple edges; this affects the applicability of the Hitting Set Conjecture.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The positive algorithmic result rests on structural properties of 1/2-hyperbolic graphs and prior approximation techniques. The hardness result rests on the external Hitting Set Conjecture as a domain assumption. No free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Hitting Set Conjecture
Invoked to rule out linear-time algorithms for 1-hyperbolic graphs.

pith-pipeline@v0.9.0 · 5563 in / 1231 out tokens · 98099 ms · 2026-05-09T13:42:32.466947+00:00 · methodology

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs

Core claim

Load-bearing premise

discussion (0)