mardi 2 juin 2026

par BUTEL Nathalie

Dibyayan Chakraborty, maître de conférence à l' Université de Leeds, UK, donnera un séminaire en visioconférence le mardi 2 juin 2026 à 14h au Centre Inria d'Université Côte d'Azur dans la salle Euler violet.

TITLE : 

Additive approximation algorithm for geodesic centers in δ-hyperbolic graphs 

ABSTRACT : 

For an integer k ≥ 1, the objective of k-Geodesic Center is to find a set C of k isometric paths such that the maximum distance between any vertex v and C is minimized. Introduced by Gromov, δ-hyperbolicity measures how tree-like a graph is from a metric point of view. Our main contribution in this paper is to provide an additive O(δ)-approximation algorithm for k-Geodesic Center on δ-hyperbolic graphs. On the way, we define a coarse version of the pairing property introduced by Gerstel & Zaks (Networks, 1994) and show it holds for δ-hyperbolic graphs. This result allows us to reduce the k-Geodesic Center problem to its rooted counterpart, a main idea behind our algorithm. We also adapt a technique of Dragan & Leitert (TCS, 2017) to show that for every k ≥ 1, k-Geodesic Center is NP-hard even on partial grids. This is a joint work with Yann Vaxès (University of Marseille).