Parameterized algorithms for eccentricity shortest path problem

DOI10.1007/978-3-031-34347-6_7MaRDI QIDQ6182893zbMATH OpenFDO

Authors Sriram Bhyravarapu, Satyabrata Jana, Lawqueen Kanesh, Saket Saurabh, Shaily Verma

Publication date 22 December 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2304.03233

zbMATH Keywords

eccentricityfeedback vertex setFPTshortest pathW[2-hardness]

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Abstract: 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 $vinV(G)$, there is a vertex $winP$ such that $d_G(v,w)leqell$, 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, Kuv 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.

Cites work

• Graph theory
• Minimum degree and dominating paths
• Minimum eccentricity shortest path problem with respect to structural parameters
• Minimum eccentricity shortest path problem: an approximation algorithm and relation with the k-laminarity problem
• Minimum eccentricity shortest paths in some structured graph classes
• On the minimum eccentricity shortest path problem
• Parameterized algorithms

Cited in

(3)

• On the minimum eccentricity shortest path problem
• ECO method and hill-free generalized Motzkin paths
• Additive approximation algorithm for geodesic centers in -hyperbolic graphs

This page was built for publication: Parameterized algorithms for eccentricity shortest path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6182893)