Parameterized Algorithms for Eccentricity Shortest Path Problem

Given an undirected graph G = (V, E) and an integer l, the Eccentricity Shortest Path (ESP) problem asks to check if there exists a shortest path P such that for every vertex v is an element of V (G), there is a vertex w is an element of P such that d(G)(v, w) <= l, where d(G)(v, w) represents the distance between v and w in G. Dragan and Leitert [Theor. Comput. Sci. 2017] studied the optimization version of this problem which asks to find the minimum l for ESP and showed that it is NP-hard even on planar bipartite graphs with maximum degree 3. They also showed that ESP is W[2]-hard when parameterized by l. On the positive side, Kucera and Suchy [IWOCA 2021] showed that ESP is fixed-parameter tractable (FPT) when parameterized by modular width, cluster vertex deletion set, maximum leaf number, or the combined parameters disjoint paths deletion set and l. It was asked as an open question in the same paper, if ESP is FPT parameterized by disjoint paths deletion set or feedback vertex set. We answer these questions and obtain the following results: 1. ESP is FPT when parameterized by disjoint paths deletion set, or the combined parameters feedback vertex set and l. 2. A (1 + epsilon)-factor FPT approximation algorithm when parameterized by the feedback vertex set number.