Exact algorithms and computational complexity for the strong geodetic set problem

Abstract

We studied the strong geodetic set problem (SGSP), an NP-Complete convexity problem in graphs that asks for a minimum strong geodetic set. A strong geodetic set is a vertex set in which it is possible cover all vertices of the graph by assigning a shortest path for each vertex pair at the set. We achieved results concerning the computation complexity of the problem. Our approach was based mainly on analyzing the problem for different graph classes, then it was possible to construct a comprehensive graph class hierarchy specifying the complexity of the problem for bipartite graphs, co-bipartite graphs, chordal graphs, block graphs, threshold graphs, cactus graphs and trees. In addition, we stated that the SGSP is fixed parameter tractable when the parameters are the graph's diameter and the natural parameter together. Besides that, we proved that the SGSP parameterized by the diameter is not in XP, strengthening the previous result. Moreover, we defined the strong geodetic set recognition problem (SGSRP), which can be seen as a subproblem of the SGSP. We obtained a proof of the NP-Completeness of the problem, increasing the understanding of the SGSP and also gathering knowledge about a new convexity problem with interesting applications. Finally, given the strong relation between the two cited problems, we could also derive the complexity status of the SGSRP for bipartite graphs, block graphs, graphs with diameter 2, split graphs, cacti graphs and trees.