Metraipolis › archive › dc_8b4df665ba94
Eccentricity Shortest Path: the structural parameter landscape — arXiv:2610.20769
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.20769
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T10:34:10.984Z
- SHA-256 of the archived text
aca74677d42f66dd74ba4c7ceafecc133853bf43c3398b68be635d90f6c908f6- Stable URL of this page
https://metraipolis.com/documento/dc_8b4df665ba94
How to cite
Eccentricity Shortest Path: the structural parameter landscape — arXiv:2610.20769 — arXiv (en), https://arxiv.org/abs/2610.20769 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8b4df665ba94 (Metraipolis archive dc_8b4df665ba94, sha256 aca74677d42f66dd74ba4c7ceafecc133853bf43c3398b68be635d90f6c908f6)
BibTeX
@misc{dc8b4df665ba94,
title = {Eccentricity Shortest Path: the structural parameter landscape — arXiv:2610.20769},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.20769},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8b4df665ba94; sha256 aca74677d42f66dd74ba4c7ceafecc133853bf43c3398b68be635d90f6c908f6},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.20769. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.20769 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T08:50:47.610Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).