On the computational complexity of the strong geodetic recognition problem

¹ Centro de Ciências e Tecnologia, Universidade Federal do Cariri, Juazeiro do Norte, Brazil
² Departamento de Ciência da Computaçço, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil
³ Faculty of Logistics, Molde University College, Molde, Norway

^* Corresponding author: viniciussantos@dcc.ufmg.br

Received: 27 February 2023
Accepted: 30 May 2024

Abstract

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 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.