Eccentricity Shortest Path: the structural parameter landscape
Abstract
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 latter two. Consequently, the problem is polynomial-time solvable for every fixed treewidth, answering a question of Chakraborty et al. (2026). We also derive fixed-parameter tractability for treedepth and XP membership for diameter from earlier algorithms. We prove W[3]-hardness for cutwidth, and hence pathwidth and treewidth, even on graphs of maximum degree at most five; W[2]-hardness for vertex clique-cover number; and NP-hardness on graphs of tree-independence number at most two. For maximum leaf number ℓ, we obtain an O(ℓ4)-bit compression and a polynomial kernel. Finally, unless NP⊆coNP/poly, we exclude polynomial kernels for bandwidth, feedback edge number, vertex-deletion distance to a clique, and vertex cover number. The last bound also excludes polynomial kernels for vertex-deletion distance to proper interval graphs.
Related
- Local network evolution rules driving shortest path multiplicity
- Shortest-Path Multiplicity Heterogeneity as a Graph Diagnostic for Radial Organization in Sampled Geometries
- Occupation-Weighted Performance Bounds for Rollout Policies in Stochastic Shortest Path Problems
- Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers
- The Restricted Inverse Optimal Value Problem on Shortest Path under l∞ Norm on Trees
BibTeX
@misc{babu2026eccentricity,
title = {{Eccentricity Shortest Path: the structural parameter landscape}},
author = {Anand Babu and Ashwin Jacob and Hitendra Kumar and R. B. Sandeep},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20769},
eprint = {2610.20769},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20769},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Eccentricity Shortest Path: the structural parameter landscape
AU - Anand Babu
AU - Ashwin Jacob
AU - Hitendra Kumar
AU - R. B. Sandeep
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20769
UR - https://arxiv.org/abs/2610.20769
AB - 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 latter two. Consequently, the problem is polynomial-time solvable for every fixed treewidth, answering a question of Chakraborty et al. (2026). We also derive fixed-parameter tractability for treedepth and XP membership for diameter from earlier algorithms. We prove W[3]-hardness for cutwidth, and hence pathwidth and treewidth, even on graphs of maximum degree at most five; W[2]-hardness for vertex clique-cover number; and NP-hardness on graphs of tree-independence number at most two. For maximum leaf number ℓ, we obtain an O(ℓ^4)-bit compression and a polynomial kernel. Finally, unless NP⊆coNP/poly, we exclude polynomial kernels for bandwidth, feedback edge number, vertex-deletion distance to a clique, and vertex cover number. The last bound also excludes polynomial kernels for vertex-deletion distance to proper interval graphs.
ER -