# Eccentricity Shortest Path: the structural parameter landscape

Preprint · Anand Babu, Ashwin Jacob, Hitendra Kumar, R. B. Sandeep

- Archive id: arxiv:2610.20769
- Published: 2026-10-14
- arXiv: https://arxiv.org/abs/2610.20769
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.20769
- PDF: https://arxiv.org/pdf/2610.20769
- Provenance: arxiv

## 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 $\\mathsf{W}\[3\]$-hardness for cutwidth, and hence pathwidth and treewidth, even on graphs of maximum degree at most five; $\\mathsf{W}\[2\]$-hardness for vertex clique-cover number; and NP-hardness on graphs of tree-independence number at most two. For maximum leaf number $\\ell$, we obtain an $O(\\ell^4)$-bit compression and a polynomial kernel. Finally, unless $\\mathsf{NP}\\subseteq\\mathrm{coNP}/\\mathrm{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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.