On the Computational Complexity of the Strong Geodetic Recognition Problem
share
A strong geodetic set of a graph G=(V,E) is a vertex set S ⊆ V(G) in which it is possible to cover all the remaining vertices of V(G) ∖ 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 ⊆ 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.
READ FULL TEXT