{"id":"arxiv:2608.13158","kind":"preprint","title":"Minimum eccentricity shortest paths of $K_{2,3}$-minor-free graphs","authors":["Dibyayan Chakraborty","Sandip Das","Sk Samim Islam","Ritam Manna Mitra","Saumya Sen"],"author_count":5,"year":2026,"published":"2026-08-13","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2608.13158","nct_id":null,"source_url":"https://arxiv.org/abs/2608.13158","archive_url":"https://space-kitty.com/papers/arxiv:2608.13158","updated":"2026-08-13","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2608.13158","abstract":"Given a simple, undirected, and unweighted graph $G$, and an integer $R$, the objective of the \\textsc{Minimum Eccentricity Shortest Path (MESP)} is to decide whether there exists an \\emph{isometric path} $P$ in $G$ such that the distance from every vertex in the graph to its nearest vertex in $P$ is at most $R$. In this paper, we prove that MESP admits an $O(n^4)$-time algorithm on $K_{2,3}$-minor-free graphs. Our algorithm has a cubic running time when the inputs are restricted to a cactus.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}