Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00601
Parameterized Complexity of Geodetic Set
Vol. 26, no. 4, pp. 401419, 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 NPhard ${\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, pathwidth, and solution size, combined.
On the other side, we develop fixedparameter algorithms with respect to the feedback edge number, the treedepth, and the modularwidth of the input graph.
This work is licensed under the terms of the CCBY license.

Submitted: October 2021.
Reviewed: April 2022.
Revised: June 2022.
Accepted: June 2022.
Final: July 2022.
Published: July 2022.
Communicated by
Yoshio Okamoto

Journal Supporters
