Algorithms and Hardness for Geodetic Set on Tree-Like Digraphs

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.