Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number

Abstract

In the \textsc{Geodetic Set} problem, the input consists of a graph $G$ and a positive integer $k$. The goal is to determine whether there exists a subset $S$ of vertices of size $k$ such that every vertex in the graph is included in a shortest path between two vertices in $S$. Kellerhals and Koana [IPEC 2020; J. Graph Algorithms Appl 2022] proved that the problem is $\W[1]$-hard when parameterized by the pathwidth and the feedback vertex set number of the input graph. They posed the question of whether the problem admits an $\XP$ algorithm when parameterized by the combination of these two parameters. We answer this in negative by proving that the problem remains \NP-hard on graphs of constant pathwidth and feedback vertex set number.