Parameterized Complexity of Geodetic Set
Vol. 26, no. 4, pp. 401-419, 2022. Regular paper.
Abstract A vertex set $S$ of a graph $G$ is geodetic if every vertex of $G$ lies on a shortest path between two vertices in $S$. Given a graph $G$ and $k \in \mathbb{N}$, the NP-hard ${\rm G{\small EODETIC}~S{ \small ET}}$ problem asks whether there is a geodetic set of size at most $k$. Complementing various works on ${\rm G{\small EODETIC}~S{ \small ET}}$ restricted to special graph classes, we initiate a parameterized complexity study of ${\rm G{\small EODETIC}~S{ \small ET}}$ and show, on the one side, that ${\rm G{\small EODETIC}~S{ \small ET}}$ is $W[1]$-hard when parameterized by feedback vertex number, path-width, and solution size, combined. On the other side, we develop fixed-parameter algorithms with respect to the feedback edge number, the tree-depth, and the modular-width of the input graph.

 This work is licensed under the terms of the CC-BY license.
Submitted: October 2021.
Reviewed: April 2022.
Revised: June 2022.
Accepted: June 2022.
Final: July 2022.
Published: July 2022.
Communicated by Yoshio Okamoto
article (PDF)