Abstract:
In the Geodetic Set problem, an input is a digraph
and integer
, and the objective is to decide whether there exists a vertex subset
of size
such that any vertex in
lies on a shortest path between two vertices in
. The problem has been studied on undirected and directed graphs from both algorithmic and graph-theoretical perspectives.
We focus on directed graphs and prove that Geodetic Set admits a polynomial-time algorithm on ditrees, that is, digraphs with possible
-cycles when the underlying undirected graph is a tree (after deleting possible parallel edges). This positive result naturally leads us to investigate cases where the underlying undirected graph is ‘close to a tree’.
Towards this, we show that Geodetic Set on digraphs without
-cycles and whose underlying undirected graph has feedback edge set number
, can be solved in time
, where
is the number of vertices. To complement this, we prove that the problem remains NP-hard on DAGs (which do not contain
-cycles) even when the underlying undirected graph has constant feedback vertex set number. Our last result significantly strengthens the result of Araújo and Arraes [Discrete Applied Mathematics, 2022] that the problem is NP-hard on DAGs when the underlying undirected graph is either bipartite, cobipartite or split.