Given an undirected graph $G=(V,E)$ and an integer $\ell$, the Eccentricity Shortest Path (ESP) asks to find a shortest path $P$ such that for every vertex $v\in V(G)$, there is a vertex $w\in P$ such that $d_G(v,w)\leq \ell$, where $d_G(v,w)$ represents the distance between $v$ and $w$ in $G$. Dragan and Leitert [Theor. Comput. Sci. 2017] showed that the optimization version of this problem, which asks to find the minimum $\ell$ for the ESP problem, is NP-hard even on planar bipartite graphs with maximum degree 3. They also showed that ESP is W[2]-hard when parameterized by $\ell$. On the positive side, Ku\v cera and Such\'y [IWOCA 2021] showed that the problem exhibits fixed parameter tractable (FPT) behavior when parameterized by modular width, cluster vertex deletion set, maximum leaf number, or the combined parameters disjoint paths deletion set and $\ell$. It was asked as an open question in the above paper, if ESP is FPT parameterized by disjoint paths deletion set or feedback vertex set. We answer these questions partially and obtain the following results: - ESP is FPT when parameterized by disjoint paths deletion set, split vertex deletion set or the combined parameters feedback vertex set and eccentricity of the graph. - We design a $(1+\epsilon)$-factor FPT approximation algorithm when parameterized by the feedback vertex set number. - ESP is W[2]-hard when parameterized by the chordal vertex deletion set.
翻译:基于参数的偏心最短路径问题的算法
给定一个无向图G = (V,E)和整数l,偏心最短路径(ESP)问题要求找到一条最短路径P,使得对于每个顶点v∈V(G),存在一个顶点w∈P,使得d_G(v,w) ≤ l,其中d_G(v,w)表示G中v和w之间的距离。Dragan和Leitert [Theor. Comput. Sci. 2017]证明了该问题的最优化版本,该版本要求找到ESP问题的最小l,即使在最大度为3的平面二分图上,该问题也是NP难的。他们还表明,当参数为l时,ESP是W[2]-hard的。积极的方面是,Ku\v cera和Such\'y [IWOCA 2021]表明,该问题的参数化宽度与支配集、最大叶数或联合参数不相交的路径删除集和l存在固定参数跨越特性(FPT)。在上述论文中提出了以下问题,即如果将ESP参数化为不相交的路径删除集或反馈顶点集,是否可以FPT。我们部分回答了这些问题,获得了以下结果:-当将不相交的路径删除集、分割顶点删除集或联合参数反馈顶点集和图的偏心率参数化时,ESP是FPT的;-当将反馈顶点集数量参数化时,我们设计了一个$(1+\epsilon)$-近似FPT算法;-当将和弦顶点删除集参数化时,ESP是W[2]-hard的。