On the Computational Complexity of the Strong Geodetic Recognition Problem

A strong geodetic set of a graph~$G=(V,E)$ is a vertex set~$S \subseteq V(G)$ in which it is possible to cover all the remaining vertices of~$V(G) \setminus S$ by assigning a unique shortest path between each vertex pair of~$S$. In the Strong Geodetic problem (SG) a graph~$G$ and a positive integer~$k$ are given as input and one has to decide whether~$G$ has a strong geodetic set of cardinality at most~$k$. This problem is known to be NP-hard for general graphs. In this work we introduce the Strong Geodetic Recognition problem (SGR), which consists in determining whether even a given vertex set~$S \subseteq V(G)$ is strong geodetic. We demonstrate that this version is NP-complete. We investigate and compare the computational complexity of both decision problems restricted to some graph classes, deriving polynomial-time algorithms, NP-completeness proofs, and initial parameterized complexity results, including an answer to an open question in the literature for the complexity of SG for chordal graphs.

No reviews yet.

No comments yet.