2022/08/03 by Lima, Carlos V. G. C., Santos, Vinicius F. dos, Sousa, João H. G. +1 · 1 citation
#05C #90C39 #94C15 #Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2208.01796
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.