{"id":"arxiv/2610.20769","url":"https://arxiv.org/abs/2610.20769","tags":["cs.DS","math.CO"],"score":0,"title":"Eccentricity Shortest Path: the structural parameter landscape","domain":"cs.DS","source":"arxiv","authors":["Anand Babu","Ashwin Jacob","Hitendra Kumar","R. B. Sandeep"],"reviews":0,"subject":"cs.DS","summary":"The Eccentricity Shortest Path problem asks, given a connected graph and a nonnegative integer $R$, whether some shortest path is within distance $R$ of every vertex. We study its structural parameterized complexity. We give fixed-parameter algorithms for vertex-deletion distance to cographs, vertex-deletion distance to interval graphs, and bandwidth. The interval-deletion result answers a question of Bhyravarapu et al. (IWOCA 2023). We obtain XP algorithms for vertex-deletion distance to chordal graphs, clique-width, and rank-width, without requiring expressions or decompositions for the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-14","reactions":{}}