Eccentricity shortest path complexity varies by graph parameters
Eccentricity Shortest Path: the structural parameter landscape
Data Structures and Algorithms
Summary
The eccentricity shortest path problem asks if there is a shortest path that stays close to every point in a network. The authors study how the problem's difficulty changes depending on structural features of the network, such as certain ways to simplify or measure it. They identify cases where the problem can be solved efficiently and others where it is likely very hard. Their work answers some open questions and shows limits on how much the problem can be simplified.
What this means in practice
- •For graph algorithm designers: Identify graph parameters where eccentricity shortest path problems are solvable efficiently or are hard, guiding algorithm focus.
- •For network infrastructure planners: Use knowledge of network structure complexity to estimate feasibility of finding central shortest paths for monitoring or routing.
A theory result. No direct application yet.
Authors
Anand Babu, Ashwin Jacob, Hitendra Kumar, R. B. Sandeep
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.