# Algorithms and Hardness for Geodetic Set on Tree-like Digraphs

Florent Foucaud, Narges Ghareghani, Lucas Lorieau, Morteza

Mohammad-Noori, Rasa Parvini Oskuei, Prafullkumar Tale

► To cite this version:

Florent Foucaud, Narges Ghareghani, Lucas Lorieau, Morteza Mohammad-Noori, Rasa Parvini Oskuei, et al.. Algorithms and Hardness for Geodetic Set on Tree-like Digraphs. 12th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2026), Feb 2026, Dharwad, Karnataka, India. pp.179-193, 10.1007/978-3-032-17156-6_14. http://05485784

HAL Id: hal-05485784

https://hal.science/hal-05485784v1

Submitted on 30 Jan 2026

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Algorithms and Hardness for Geodetic Set on
Tree-like Digraphs

Florent Foucaud<fnref n="1" />[0000-0001-8198-693X]*, Narges Ghareghani<fnref n="2" />**, Lucas Lorieau<fnref n="1" />[0009-0006-5084-5118]***, Morteza Mohammad-Noori<fnref n="2" />†, Rasa Parvini Oskuei<fnref n="2" />, and Prafullkumar Tale<fnref n="3" />[0000-0001-9753-0523]‡

**Abstract.** In the GEODETIC SET problem, an input is a digraph $G$ and integer $k$, and the objective is to decide whether there exists a vertex subset $S$ of size $k$ such that any vertex in $V(G) \setminus S$ lies on a shortest path between two vertices in $S$. 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 2-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* 2-cycles and whose underlying undirected graph has feedback edge set number *fen*, can be solved in time $2^{O(fen)} \cdot n^{O(1)}$, where $n$ is the number of vertices. To complement this, we prove that the problem remains NP-hard on DAGs (which do not contain 2-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.

<footnote n="1">¹ Université Clermont Auvergne, CNRS, Clermont Auvergne INP, Mines Saint-Étienne, LIMOS, 63000 Clermont-Ferrand, France.</footnote>

<footnote n="2">² School of Mathematics, Statistics, and Computer Science, University of Tehran, Tehran, Iran.</footnote>

<footnote n="3">³ Indian Institute of Science Education and Research Pune, Pune, India</footnote>

<footnote>* This author was supported by the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25), the International Research Center "Innovation Transportation and Production Systems" of the I-SITE CAP 20-25, and by the ANR project GRALMECO (ANR-21-CE48-0004). E-mail: florent.foucaud@uca.fr</footnote>

<footnote>** The work of this author is based upon research funded by Iran National Science Foundation (INSF) under project No. 4032600. E-mail: ghareghani@ut.ac.ir</footnote>

<footnote>*** This author has received financial support from the CNRS through the MITI inter-disciplinary programs and the IRL ReLaX. E-mail: lucas.lorieau@limos.fr</footnote>

<footnote>† E-mail: mmnoori@ut.ac.ir</footnote>

<footnote>‡ This work is supported by INSPIRE Faculty Fellowship offered by DST, GoI, India. E-mail: prafullkumar@iiserpune.ac.in</footnote>
**Keywords:** Geodetic Set · Directed Trees · NP-hardness · Parameterized Complexity · Feedback Edge Set Number · Feedback Vertex Set Number

# 1 Introduction

Harary, Loukakos, and Tsuros [25] introduced the concept of a *geodetic set*, defined as a set *S* of vertices of an undirected graph *G* such that every vertex of *G* lies on some geodesic (shortest path) between two vertices of *S*. Since then, the problem of computing a geodetic set has been extensively studied, both from the structural and algorithmic perspectives. It has become a central topic in *geodesic convexity* in graphs [18,29], and has found applications in diverse settings. We refer the reader to [17] and the references therein for a representative list of applications. For example, computing a minimum-size geodetic set can be seen as a network design problem, where one seeks to determine optimal locations of public transportation hubs in a road network [5].

Let GEODETIC SET be the corresponding algorithmic problem of determining a smallest possible geodetic set. Harary, Loukakos, and Tsuros [25] proved that the problem is NP-hard. See [16] for the earliest rigorous proof. Later works established that the problem remains NP-hard even for restricted graph classes [4,5,6,15,17]. This has motivated the study of algorithms for structured graph classes [1,4,6,15,16,17,28]. To cope with this hardness, the problem has also been investigated through the lenses of parameterized complexity [4,20,21,26,30] and approximation algorithms [5,12]. More recently, interest in this problem has been rejuvenated, as its ‘metric-based nature’ has led to interesting conditional lower bounds in parameterized complexity [20,22,30] and enumeration complexity [3], together with related problems of a similar ‘metric-based’ nature. Here, we use the term ‘metric-based graph problem’ as an umbrella notion for graph problems whose solutions are defined using a graph metric, for example, shortest distance between two vertices in the case of GEODETIC SET.

While the majority of studies on the GEODETIC SET problem focuses on undirected graphs, the problem has also been investigated for directed graphs (digraphs). Most of the existing work on geodetic sets in digraphs has concentrated on non-algorithmic questions like determining the minimum and maximum values of these sets, as well as the range of possible values. See [7,8,9,14,19,27] and the book [29, Chapter 6]. More recently, Araújo and Arraes [2] initiated the algorithmic study of the GEODETIC SET problem for digraphs. Before presenting their results, we formally define the problem addressed in this article and compare the results for undirected and directed graphs.

**GEODETIC SET**

**Input:** A directed graph *D* and an integer *k*.

**Task:** Determine whether there exists a subset $S \subseteq V(D)$ of size *k* such that every vertex in $V(D)$ lies on some directed shortest path between two vertices in *S*.
We define a 2-cycle of $D$ as a directed cycle of length 2: a pair of vertices $u, v$ such that both arcs $(u, v)$ and $(v, u)$ are present in $D$. Note that directed graphs with 2-cycles inherit the difficulties of designing algorithms for the undirected case (since the problem is equivalent on an undirected graph $G$ and on the digraph obtained from $G$ by replacing each edge by a directed 2-cycle). Hence, the presence of 2-cycles plays a critical role when stating results for digraphs.

As noted by Araújo and Arraes [2, Sec. 6], the unique minimum-sized geodetic set of an undirected tree $T$ is equal to the set of its leaves. Define an *extremal vertex* of a digraph as a vertex that has either no incoming or no outgoing arcs, and denote by $\text{Ext}(D)$ the set of extremal vertices of $D$ (in an oriented graph, this set contains all leaves). The authors remark that in oriented trees, *i.e.* digraphs that have no 2-cycles and whose underlying undirected graph is a tree, the similar following property holds.

**Proposition 1 ([2], Proposition 6.1).** Let $D$ be an oriented tree. Then, $\text{Ext}(D)$ is a minimum geodetic set of $D$.

Using a non-trivial set of ideas and careful case analysis, the authors of [2] generalized this algorithm to digraphs without 2-cycles whose underlying undirected graph is a cactus. (A graph is called a *cactus* if each block is either an edge or a cycle, and hence every tree is a cactus graph.) We note that their case analysis holds only when the input digraph does not contain a 2-cycle. A digraph whose underlying graph is a tree is called a *ditree* [11,23]. Note that a ditree, contrary to oriented trees, might contain 2-cycles. As our first result, we present a polynomial-time algorithm for ditrees.

**Theorem 2.** *GEODETIC SET on ditrees admits a linear-time algorithm.*

This naturally leads us to investigate the problem for cases where the underlying undirected graph of the input digraph is 'close to a tree'. We consider the following two definitions of 'closeness to trees' for an undirected graph $G$: the minimum number of edges (respectively, vertices) that must be deleted from $G$ to obtain a forest. The minimum size of a set of such edges (respectively, vertices) is called the *feedback edge set number* (respectively, *feedback vertex set number*) of the graph, and is denoted by $\text{fen}(G)$ and $\text{fvn}(G)$, respectively.

Kellerhals and Koana [26] proved that the GEODETIC SET problem admits an algorithm running in time $2^{O(\text{fen}(G)^2)} \cdot n^{O(1)}$ when the input is an undirected graph. In the authors' own words, "It turns out to be quite effortful to obtain fixed-parameter tractability, requiring the design and analysis of polynomial-time data reduction rules and branching before employing the main technical trick: Integer Linear Programming (ILP) with a bounded number of variables." Improving the running time of this algorithm has remained a challenging open problem. Note that obtaining a fixed-parameter tractable algorithm parameterized by $\text{fen}$ for GEODETIC SET when the input digraph is allowed to have 2-cycles inherently encodes the difficulties encountered by the authors of [26]. As our next result, we show that a significantly faster algorithm (that does not need to use any ILP) can be obtained when considering the case in which 2-cycles are not allowed.
**Theorem 3.** *GEODETIC SET on digraphs without 2-cycles whose underlying undirected graph has feedback edge set number *f*n, admits an algorithm running in time 2*$^{O(f*n*)}$·*n*$^{O(1)}$, where *n* is the number of vertices in the input digraph.*

Finally, we turn our attention to the feedback vertex set number and show
that a fixed-parameter tractable algorithm for this parameter is not possible.
Recently, Tale [30] proved that GEODETIC SET, restricted to undirected graphs,
remains NP-hard even when the feedback vertex set fvn of the input graph is
bounded. This implies that GEODETIC SET, restricted to directed graphs with
possible 2-cycles, remains NP-hard even when the underlying undirected graph
has constant fvn. We prove that a similar result holds even when 2-cycles (which
help channel the hardness from the undirected case into the directed case), are
absent. In fact, we prove the result not only for digraphs without 2-cycles but
also for directed acyclic graphs (DAGs), which do not have directed cycles of
any length. This significantly strengthens the results of Araújo and Arraes [2],
which state that GEODETIC SET is NP-hard on DAGs even when the underlying
undirected graph is bipartite, co-bipartite, or a split graph.

**Theorem 4.** *GEODETIC SET on DAGs (which do not have 2-cycles) whose underlying undirected graph has feedback vertex set number 12, is NP-hard.*

We remark that, although our reduction is inspired by the ideas in [30], it is
significantly simpler than the one presented there.

*Outline*. Due to space constraints, we omit proofs of the results marked with (★) and refer to the upcoming full version of the paper. We start with a linear-time algorithm on ditrees in Section 2 proving Theorem 2, followed by describing the fixed-parameter tractable algorithm mentioned in Theorem 3 in Section 3. We prove Theorem 4 in Section 4 and conclude with some open problems in Section 5.

*Preliminaries.* We present general definitions and results that will be used throughout the paper. We refer to the book [10] for terminology and details on parameterized complexity.

A *directed graph* (digraph for short) *D* consists of vertex set *V*(*D*) and arc set *A*(*D*), where each arc is an ordered pair of vertices. An arc from vertex *v* to vertex *u* is denoted by *vu*, and *v* is its *tail* and *u* is its *head*. A digraph is called an *oriented graph* if it does not contain a directed 2-cycle. The *underlying undirected graph* (or simply *underlying graph*) of some digraph *D* is the graph obtained by removing the orientation of each arc of *D*. An *oriented path* of a digraph *D* is a subgraph of *D* whose underlying graph is a path. A *directed path* (or *dipath*) is an oriented path for which all arcs are oriented in the same direction. A digraph is called *strongly connected* if every pair of vertices are connected by a directed path. The *in-neighborhood* of vertex *u* is denoted by *N*⁻(*u*) and its *out-neighborhood* is denoted by *N*⁺(*u*). The in-neighborhood of a subset *S* of *V*(*D*) is *N*⁻(*S*) = (*∪*_{*u*∈*S*} *N*⁻(*u*)) \ *S*, and similarly the out-neighborhood of *S* is defined. A vertex *x* is called a *source*, if *N*⁻(*x*) = ∅, and it is called a *sink* if
$N^+(x) = \emptyset$. A vertex that is a source or a sink is called extremal. For two vertices $u$ and $v$, the set of vertices that lie in some shortest path from $u$ to $v$ is denoted by $I(u, v)$ and for a subset $S$ of $V$, the geodetic closure of $S$, denoted by $I(S)$, is the set of all vertices which lie in some shortest path between two vertices of $S$. In other words, $I(S) = \cup_{u,v \in S} (I(u, v) \cup I(v, u))$. We also say that a vertex $v$ is covered by two vertices $u$ and $w$ if $v \in I(\{u, w\})$. In a directed path $P$ from $u$ to $v$, vertices $u$ and $v$ are called the tail and the head of $P$, respectively. The vertices of $P$ which are neither the tail nor the head of $P$ are called its inner vertices. A directed acyclic graph (DAG for short) is a digraph which does not contain any directed cycle.

A vertex $v$ is transitive if, for every in-neighbor $u_1$ and out-neighbor $u_2$ of $v$, either the arc $u_1u_2$ exists, or $u_1 = u_2$.<fnref n="4" /> A vertex of a digraph is called a leaf if, in the underlying undirected graph, it has degree 1. Note that any leaf of a digraph is either a sink, a source, or transitive.

We conclude this section with the following lemma.

**Lemma 5 ([2]).** In any digraph $D$, every source, sink and transitive vertex of $D$ (in particular, every leaf of $D$) belongs to every geodetic set of $D$.

## 2 Linear-time algorithm for ditrees

In this section, we consider the problem of finding the geodetic number of a ditree and prove the following theorem.

**Theorem 2.** *GEODETIC SET on ditrees admits a linear-time algorithm.*

In the context of digraphs admitting 2-cycles, we say that a vertex of a digraph $D$ is a *leaf* of $D$ if it is a leaf of the underlying graph of $D$. When $T$ is an oriented tree, a minimum-size geodetic set (mgs for sort) may contain some non-leaf vertices: as observed in Proposition 1, in this case, an optimal mgs always consists of all sources and sinks of the tree. To prove Theorem 2, we reduce the problem to finding a mgs in directed trees where the only 2-cycles present are adjacent to some leaf of the graph. We argue then that taking all extremal vertices of the graph, in addition to the leaves contained in a 2-cycle, yields a mgs. Intuitively, the graph obtained behaves almost exactly as an oriented tree, which enables us to extend Proposition 1 naturally.

Let $S$ be a maximal strongly connected component of $D$. Then we call $S$ a *source set* if $N^-(S) \setminus S = \emptyset$. Similarly, we call $S$ a *sink set* if $N^+(S) \setminus S = \emptyset$. We can state a simple observation about sink and source sets.

**Observation 1.** Let $S$ be a source set or a sink set. Then, any two adjacent vertices of $S$ form a 2-cycle.

We define now a new graph, whose structure is very similar to an oriented tree.

<footnote n="4">⁴ Note that the latter condition was not present in the definition from [2], since the authors only considered digraphs without 2-cycles.</footnote>
**Definition 6.** Let $T$ be a ditree. We define the contracted ditree $T^c$ of $T$ by iteratively contracting every 2-cycle of $T$ that does not contain any leaf vertex into a single vertex.

In particular, in $T^c$, the only 2-cycles are adjacent to some leaf of the graph. $T^c$ is thus an oriented tree to which some leaves are contained in 2-cycles. Lemma 7 shows that in contrast to oriented trees, an mgs in a general ditree may contain vertices which are neither sources, sinks nor leaves. Then, Lemma 8 states that if all source and sink sets are either composed of a unique vertex or contain a leaf, then we can easily find a mgs in the considered ditree. In particular, this can be applied on $T^c$. Finally, Lemmas 9 and 10 justify that we can extend any mgs of $T^c$ to $T$.

**Lemma 7 (*)**. Let $T$ be a ditree and let $S$ be a source set or sink set of $T$. Then, every geodetic set of $T$ includes at least one vertex from $S$.

**Lemma 8 (*)**. Let $T$ be a ditree for which any source (resp. sink) set of size at least 2 contains a leaf. Let $S \subseteq V(T)$ be the set of all sink (resp. source) vertices and all leaves of $T$. Then, $S$ is a geodetic set of $T$ of minimum size.

**Lemma 9.** Let $T$ be a ditree and $S$ be a source set or sink set of size at least 2 that contains no leaves. Suppose $M$ is an mgs for $T$ that includes exactly one vertex from $S$. Define $N \subseteq V(T)$ as the set obtained from $M$ by replacing the unique vertex of $S$ with any other vertex of $S$. Then, $N$ is also an mgs for $T$.

*Proof*. Without loss of generality, assume that $S$ is a source set. Arguments are similar for sink sets. Let $u \in S \cap M$, we first show that the lemma holds when $u$ is replaced by one of its neighbours in $S$. Let $P_1, \dots, P_m$ be all maximal directed paths starting from $u$ and ending at some vertex of $M$. Choose a vertex $v \in S$ such that $v$ is an out-neighbour of $u$. Since $S$ is a source set, $v$ is also an in-neighbour of $u$. Because $M$ is an mgs and $S$ is a source set, some paths among $P_1, \dots, P_m$ must contain $v$. Let $P_1, \dots, P_i$ denote exactly those paths that contain $v$. Since $T$ is a ditree, each such path necessarily begins with the arc $uv$. Moreover, as $u$ is not a leaf, there should also exist paths among $P_1, \dots, P_m$ that do not contain $v$. Assume without loss of generality, that $i < m$ and $P_{i+1}, \dots, P_m$ are all these paths.

Now, for each $1 \le j \le i$, let $P'_j$ be the path obtained from $P_j$ by deleting the vertex $u$ and the arc $uv$. For each $j$ with $i+1 \le j \le m$, let $P'_j$ be the directed path obtained from $P_j$ by prepending the arc $uv$. It follows that the set $N$ covers exactly the same set of vertices as $M$, and hence $N$ also is an mgs.

Next, we show that the lemma remains valid if $u$ is replaced by some vertex $w \in S$ that is not a neighbour of $u$. Since $S$ is a source set, there is a directed path from $u$ to $w$ all whose internal vertices are in $S$. Moreover, each arc in this path is part of a 2-cycle in $T$. Therefore, starting from $u$, we may successively replace the current vertex by its neighbour along the path, until reaching $w$. At each step, the resulting set is an mgs and thus, after the final replacement, the set obtained by substituting $u$ with $w$ is also an mgs, as required. $\square$
**Lemma 10.** Let $T$ be a ditree and $S = \{S_1, S_2, \dots, S_t\}$ be the set of all source sets and sink sets of $T$ which do not contain any leaf. Let $\mathcal{L}$ be the set consisting of all leaves of $T$ and $M$ be a subset of $V(T)$ that contains $\mathcal{L}$ and exactly one vertex from each $S_i$. Then, $M$ is an mgs for $T$.

*Proof.* We prove the theorem using induction on the number of vertices of $T$. If $T$ has 2 vertices, then every vertex of $T$ is a leaf. Using Lemma 5, $\mathcal{L}$ is an mgs for $T$. By the induction hypothesis, suppose that the theorem is true for any ditree of size less than $n$. Let $T$ be a ditree with $n$ vertices. If each source (resp. sink) set of $T$ of size at least 2 contains a leaf, then each source (resp. sink) set which does not contain a leaf is a source (resp. sink) vertex. So in this case, the theorem holds, using Lemma 8.

Now, without loss of generality, suppose that $S_t \in S$ is a source set and it has at least two vertices. Let $u, v$ be two vertices in $S_t$ which are adjacent and $T'$ be a ditree obtained from $T$ by contracting the edge between $u$ and $v$. Let $w$ be the new vertex in $T'$ that replaces two vertices $u$ and $v$ of $T$. Note that $T'$ is a ditree with the same set of leaves as $T$, and with the same set of source (resp. sink) sets as $T$, except that $S_t$ is replaced by $S'_t$, where $S'_t = (S_t \setminus \{u, v\}) \cup \{w\}$. Hence, by the induction hypothesis, there is an mgs of $T'$ that contains all leaves and a vertex from each of the set $S_1, S_2, \dots, S'_t$.

By Lemma 9, we conclude that a subset of vertices of $T'$ that contains all leaves of $T'$ and an arbitrary vertex from each of the set $S_1, S_2, \dots, S'_t$ is an mgs.

Let $P'_1, \dots, P'_r$ be the set of all maximal directed paths in $T'$ starting from $w$. Since $w$ is not a leaf, $r \ge 2$. One can see that the end-vertex of each of these paths is either a leaf or belongs to a sink set. Moreover, no two of these paths terminate at the same sink set; Otherwise the underlying undirected graph would contain a cycle, which is impossible. Since $T'$ has an mgs which contains all leaves and exactly one vertex from each source (resp. sink) set which does not contain any leaf, using Lemma 9, $T'$ has an mgs, $M'$, which contains $w$ and the end-vertices of each path $P'_1, \dots, P'_r$. Define $M = M' \setminus \{w\} \cup \{u\}$. We claim that $M$ is an mgs for $T$. Since $T$ and $T'$ have the same set of leaves and the same number of sink (resp. source) sets, Lemma 8 implies that every mgs of $T$ contains at least $|M'|$ vertices. Therefore, it remains to show that $M$ is a geodetic set for $T$.

Since $u$ and $v$ are in a same source set, $T$ contains both arcs $uv$ and $vu$. Since $M'$ is an mgs for $T'$, each vertex of $T$ other than $v$ is covered by a path with both ends in $M$. Now, it suffices to show that $v$ is covered by some path with ends in $M$ (note that $T$ is a ditree, so each path is a shortest path between its end vertices), Now, we claim that $v$ belongs to some $P_i$, $1 \le i \le r$. If not, $T \setminus \{v\}$ is connected and this happens only if $v$ is a leaf, which is not the case, a contradiction. $\square$

*Proof (of Theorem 2).* By Lemma 10, every mgs of $T$ contains all leaves and an arbitrary vertex of any source (sink) set that does not contain any leaf. Since any leaf in $T$ is also a leaf in $T^c$ and vice-versa, the algorithm proceeds as follows. First, we construct the contracted ditree $T^c$ from $T$ in linear time by contracting every 2-cycle that is not incident with a leaf. Then, we determine all source (resp.
sink) vertices (and the corresponding source (sink) sets in $T$), and leaves of $T^c$, which can also be done in linear time by examining the in-degree and out-degree of each vertex. Since each step requires only linear time in the number of vertices and edges, the overall complexity is $O(|V(T)| + |E(T)|)$. $\square$

## 3 Algorithm parameterized by feedback edge set number

In this section, we present an algorithm solving GEODETIC SET parameterized by the feedback edge set number of the input graph and prove Theorem 3.

**Theorem 3.** *GEODETIC SET on digraphs without 2-cycles whose underlying undirected graph has feedback edge set number fen, admits an algorithm running in time $2^{O(fen)} \cdot n^{O(1)}$, where n is the number of vertices in the input digraph.*

We introduce useful notions from [13]. A *core vertex* is a vertex of degree at least 3. A *core path* of digraph $D$ is a path in the underlying graph of $D$ between two core vertices with only degree 2 internal vertices. Note that both endpoints are allowed to be the same core vertex: in this case, we call the core path a *core cycle*. We call *proper core path* a core path whose endpoints are two different core vertices. A *leg* of the underlying graph of $D$ is a (non-empty) path between a core vertex and a leaf in said graph. The *base graph* of some undirected graph $G$ is the graph obtained by removing iteratively leaves from $G$ until no leaf is present. We say that the base graph of a digraph $D$ is the base graph of its underlying undirected graph. Note that a vertex of a base graph is either a core vertex, or an inner vertex of some core path. The following observation comes from [26, Observation 5].

**Observation 2.** *The base graph of any undirected graph $G$ has at most $2\text{fen}(G) - 2$ core vertices and at most $3\text{fen}(G) - 3$ core paths.*

We say that the *base digraph* $D_b$ of $D$ is the subgraph of $D$ such that its underlying graph is the base graph of $D$. A *hanging tree* of the underlying graph of $D$ is the union of some legs removed to form the base graph of $D$ so that the union of those legs forms a connected component. The *root* of a hanging tree of $D$ is the vertex of the base graph that was linked to the last removed leg of the hanging tree considered. It is easily seen that the underlying undirected graph of $D$ can be decomposed into its base graph and a set of maximal hanging trees. A *hanging ditree* of $D$ is a subgraph of $D$ such that its underlying graph is a hanging tree of $D$, and its root is the root of the associated hanging tree. Similarly, $D$ can be decomposed into its base digraph and a collection of maximal hanging ditrees. We call an *oriented core path* any core path of the base graph of $D$ whose edges are oriented based on the orientations in $D$. If an oriented core path forms a directed path in $D$, we call it a *core dipath*.

First, we will argue that deciding which vertices to take in a solution in the hanging ditrees of $D$ is not difficult, using the following observation.

**Observation 3 (★).** Let $v$ be a vertex of a hanging ditree $T$ of $D$ rooted in $r$.
- If $v$ has an outgoing arc, $v$ can either reach $r$ or a sink $w \in V(T)$.

- If $v$ has an incoming arc, $v$ can be reached by either $r$ or a source $u \in V(T)$.

**Claim 1** (★) Let $D$ be a digraph with $S^0$ its set of extremal vertices. Suppose $S$ is a geodetic set of $D$. Then, $S' = (S \cap V(D_b)) \cup S^0$ is a geodetic set of $D$.

Claim 1 identifies which vertices of hanging ditrees are part of minimum geodetic sets, so we next focus on vertices of oriented core paths. We identify three different cases, depending on the number of extremal vertices present in the considered oriented core path. Note that when there is no extremal vertex among the inner vertices of an oriented core path, it is in fact a core dipath.

**Claim 2** Let $D$ be a digraph and $S^0$ the set of extremal vertices of $D$. Consider an oriented core path $P$ of $D$ and denote by $V_P$ its inner vertices. Number them as $V_P = \{v_1, \dots, v_l\}$ so that two neighbors in $P$ have consecutive indexes. Suppose that $|S^0 \cap V_P| \ge 2$, and denote by $v_i$ (respectively $v_j$) the vertex with minimum index (respectively with maximum index) of $S^0 \cap V_P$. We have $\{v_i, \dots, v_j\} \subseteq I(S^0)$ and there exists an mgs $S$ of $D$ so that $V_P \cap S = V_P \cap S^0$.

*Proof.* We argue that for any $k \in [i, j]$, $v_k$ is covered by two vertices of $S^0$. Indeed, either $v_i$ and $v_j$ are the only two extremal vertices of $V_P$, and then there exists a dipath between the two covering all considered vertices, or there exist other extremal vertices between $v_i$ and $v_j$. Consider $v_m$ the vertex with minimum index among those vertices. If $v_i$ is a sink, then $v_m$ is a source (and vice versa), so if $k \in [i, m]$, $v_k \in I(v_i, v_m)$, otherwise one can apply recursively this argument with vertices $v_m$ and $v_j$.

Suppose now that $S$ is an mgs of $D$, and that some vertex $v_p$ belongs to $(V_P \cap S) \setminus S^0$. Since $\{v_i, \dots, v_j\} \subseteq I(S^0)$, if $i < p < j$, $S \setminus \{v_p\}$ is still a geodetic set, which is in contradiction with the minimality of $S$. Suppose then without loss of generality that $p < i$. Since $S$ is a geodetic set, the core vertex $v \overleftarrow{v}$ neighboring $v_1$ is either in $S$ or covered by a shortest path starting at some vertex $u \in S$ and ending at some vertex $w \in S$. In the former case, vertices $v_1, \dots, v_i$ are covered by the unique shortest path between $v \overleftarrow{v}$ and $v_i$ and $v_p$ can be removed from $S$ as above. In the latter case, consider $S' = (S \setminus \{v_p\}) \cup \{v \overleftarrow{v}\}$. Any shortest path for which $v_p$ is an endpoint can either be extended to a shortest path with $v \overleftarrow{v}$ as an endpoint, or goes through $v \overleftarrow{v}$. Thus, $S'$ is also an mgs of $D$. The same reasoning applies if $j < p$ by considering $v \overleftarrow{v}$, the core vertex neighboring $v_l$. $\square$

**Claim 3** (★) Let $P$ be an oriented core path of some digraph $D$ and denote by $V_P$ the inner vertices of $P$. Number vertices of $P$ such that $V_P = \{v_1, \dots, v_l\}$. Suppose that $|V_P \cap S^0| = 1$ and denote the vertex of $V_P \cap S^0$ by $v_p$. There exists an mgs $S$ of $D$ such that $|V_P \cap S| \le 3$ and $V_P \cap S \subseteq \{v_1, v_p, v_l\}$. In particular, $V_P \cap S$ contains at most two non-extremal vertices.

**Claim 4** (★) Let $P$ be a core dipath of some digraph $D$. Denote by $V_P$ the inner vertices of $P$ and number them in the order induced by the arcs of the dipath so that $V_P = \{v_1, \dots, v_l\}$. There exists an mgs $S$ of $D$ such that $V_P \cap S \subseteq \{v_1\}$.
Claims 2 to 4 imply an upper bound of two non-extremal vertices that can be part of an mgs in any oriented core path of D. Define $V_C$ as the set of core vertices of D and $V_I$ as the set of inner vertices of oriented core paths that are neighbors of vertices of $V_C$.

**Lemma 11.** Let D be a digraph, with $S^0$ its set of extremal vertices. There exists an mgs S of D such that $S \subseteq V_C \cup V_I \cup S^0$, and $|S \setminus S^0| \le 8\text{fen}(D) - 8$.

*Proof.* By Claims 2 to 4, we can suppose that vertices of $S'$ belonging to the base digraph of D are in $V_C \cup V_I \cup S^0$. We can then apply Claim 1 on $S'$ to obtain the geodetic set $S = (S' \cap V(D_b)) \cup S_0$ where $D_b$ is the base digraph of D. It follows that $S \subseteq V_C \cup V_I \cup S^0$. Let $P^c$ the set of core paths of $D_b$. Again by Claims 2 to 4, we have $|V_C \cup V_I| \le |V_C| + 2|P^c|$, and by Observation 2, we obtain $|S \setminus S^0| \le 8\text{fen}(D) - 8$. $\square$

We can now describe the algorithm solving GEODETIC SET parameterized by the feedback edge set number of the underlying undirected graph of the input digraph. This algorithm guesses the vertices to add in a solution among vertices in $V_C \cup V_I$. The algorithm can be stated as follows:

- For all subsets $S^1$ of $V_C \cup V_I$, if $S = S^0 \cup S^1$ is a geodetic set of D, mark S

- Return the marked set S of minimum size.

*Proof (of Theorem 3).* The correctness of the algorithm is clear from Lemma 11. The running time follows, since by Lemma 11, we have $|V_C \cup V_I| \le 8\text{fen}(D) - 8$. Thus, the algorithm checks $2^{\text{O}(\text{fen}(D))}$ different vertex sets. Each check is polynomial-time in $n$ since GEODETIC SET belongs to NP. $\square$

# 4 NP-hardness on restricted DAGs

In this section, we sketch the proof of Theorem 4. We present a reduction from the classic NP-complete problem 3-DIMENSIONAL MATCHING [24]. In this problem, an input is a ground set $U$ partitioned in three sets $X^\alpha, X^\beta$ and $X^\gamma$ such that $|X^\alpha| = |X^\beta| = |X^\gamma| = n$ and a collection of 3D edges $E \subseteq X^\alpha \times X^\beta \times X^\gamma$. The objective is to decide if there exists a set $S$ of $n$ edges of $E$ so that any element of $U$ is covered by an edge of $S$.

*Reduction.* Consider an instance of 3-DIMENSIONAL MATCHING with a ground set $U$ and its partition in three sets $X^\alpha, X^\beta$ and $X^\gamma$, and an edge set $E$. In the following, the notation $\delta$ will designate any of the letters $\alpha, \beta$ or $\gamma$. Number the vertices of $X^\delta$ so that $X^\delta = \{x_1^\delta, \dots, x_n^\delta\}$ and denote by $m$ the cardinality of $E$. We construct a digraph $D$ as follows:

**Edge vertices.** Add $n$ sets $M_1, \dots, M_n$ of $m$ vertices, each corresponding to some edge of $E$. Denote by $u_i^e$ the vertex in $M_i$ associated with edge $e$. Add also for $1 \le i \le n$ a vertex $d_i$ and an arc from any vertex in $M_i$ to $d_i$.
**Ensuring edge vertices are covered.** Add three vertices $a, b$ and $c$ and connect them as follows:

- Add arcs from $a$ to each vertex in $\bigcup_{1 \le i \le n} M_i$.

- Add arcs from each vertex in $\bigcup_{1 \le i \le n} M_i$ to $b$.

- Add arcs from each vertex in $\{d_i | 1 \le i \le n\}$ to $c$.

- Add an arc from $a$ to $c$.

**Element vertices.** Add vertices $v_i^\delta$, $w_i^\delta$ and $t_i^\delta$ associated with the element $x_i^\delta$ in $X^\delta$. Add arcs from $w_i^\delta$ to $v_i^\delta$ and from $t_i^\delta$ to $v_i^\delta$.

**Encoding adjacency.** Add nine vertices $\alpha_1, \alpha_2, \alpha_3, \beta_1, \beta_2, \beta_3, \gamma_1, \gamma_2, \gamma_3$ and add an outgoing pendant vertex to each of them. For $i \in \{1, 2, 3\}$, denote by $\delta_i^t$ the pendant vertex associated with $\delta_i$. Denote by $e$ some edge of $E$ such that $e = (x_i^\alpha, x_j^\beta, x_k^\gamma)$ and call $m$ any of its associated vertices in $\bigcup_{1 \le i \le n} M_i$. Define $\lambda = m^2$. We add some paths of defined length as follows:

- Add a path of length $\lambda^2 - i\lambda$ from $m$ to $\alpha_1$, a path of length $\lambda^2$ from $m$ to $\alpha_2$, and a path of length $\lambda^2 + j\lambda$ from $m$ to $\alpha_3$;

- Add a path of length $\lambda^2 - j\lambda$ from $m$ to $\beta_1$, a path of length $\lambda^2$ from $m$ to $\beta_2$, and a path of length $\lambda^2 + j\lambda$ from $m$ to $\beta_3$

- Add a path of length $\lambda^2 - k\lambda$ from $m$ to $\gamma_1$, a path of length $\lambda^2$ from $m$ to $\gamma_2$, and a path of length $\lambda^2 + k\lambda$ from $m$ to $\gamma_3$;

- For any $\delta \in \{\alpha, \beta, \gamma\}$, add a path of length $\lambda^2 + l\lambda$ from $\delta_1$ to $w_l^\delta$, a path of length $\lambda^2$ from $\delta_2$ to $w_l^\delta$, a path of length $\lambda^2$ from $\delta_2$ to $t_l^\delta$ and a path of length $\lambda^2 - l\lambda$ from $\delta_3$ to $w_l^\delta$.

**Ensuring the edge paths are covered.** For each path from an edge vertex of $\bigcup_{1 \le i \le n} M_i$ to a vertex $\delta_i$ for $i \in \{1, 2, 3\}$ a pendant outgoing vertex to the vertex right before $\delta_i$ in said path.

**Shortcutting the vertex a.** Add all arcs from $a$ to vertices $v_i^\delta$ associated with elements of $U$.

Figure 1 illustrates the main component of the obtained graph, namely the edge vertices and the encoding of adjacencies described above. We argue that there exists a solution to 3-DIMENSIONAL MATCHING for the original instance if and only if there exists a geodetic set of size $6nm+4n+10$ in $D$. The proof follows from the correctness of the reduction (which is presented in the full version) and the fact that deleting vertices $\alpha_1, \alpha_2, \alpha_3, \beta_1, \beta_2, \beta_3, \gamma_1, \gamma_2, \gamma_3, a, b$ and $c$ removes any cycle in the underlying graph of $D$.

# 5 Conclusion

We continued the study of GEODETIC SET for digraphs. As directions for further research, it would be interesting to extend our algorithm for ditrees to more general classes of digraphs. For instance, what can be said about directed cactus graphs (dicactii)? An algorithm for directed cactus graphs without 2-cycles (oriented cactii) was given in [2]. More broadly, one could consider directed outerplanar graphs. Note that an algorithm for undirected outerplanar graphs appears in [28]. Regarding parameterized complexity, it is natural to ask whether a polynomial kernel exists with respect to the feedback edge set number of the underlying undirected graph. This remains open even for undirected graphs [26].
<figure><img src="image_2.png" /><figcaption>Fig. 1: A partial representation of the digraph *D* constructed during the reduction. Dashed arcs represent paths of length greater than one. Red arcs between a vertex and a vertex set mean that there exists such an arc for all vertices in the vertex set. Filled vertices are extremal vertices of *D*, that belong to any geodetic set. Arcs adjacent to vertices $\delta_i$ are represented for only one edge vertex and vertices associated with three different elements, each of them belonging to a different partition set of *U*. Pending vertices to $\delta_i$ and paths from edge vertices to $\delta_i$ are not represented.</figcaption></figure>
References

1. Ahn, J., Jaffke, L., Kwon, O., Lima, P.T.: Well-partitioned chordal graphs. Discrete Mathematics 345(10), 112985 (2022)

2. Araújo, J., Arraes, P.S.M.: Hull and geodetic numbers for some classes of oriented graphs. Discrete Applied Mathematics 323, 14–27 (2022)

3. Bergougnoux, B., Defrain, O., Mc Inerney, F.: Enumerating minimal solution sets for metric graph problems. In: Proc. of the 50th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2024). Lecture Notes in Computer Science, Springer (2024)

4. Chakraborty, D., Das, S., Foucaud, F., Gahlawat, H., Lajou, D., Roy, B.: Algorithms and complexity for geodetic Sets on planar and chordal graphs. In: 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 181, pp. 7:1–7:15. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2020)

5. Chakraborty, D., Foucaud, F., Gahlawat, H., Ghosh, S.K., Roy, B.: Hardness and approximation for the geodetic set problem in some graph classes. In: Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020). Lecture Notes in Computer Science, vol. 12016, pp. 102–115. Springer International Publishing, Cham (2020)

6. Chakraborty, D., Gahlawat, H., Roy, B.: Algorithms and complexity for geodetic sets on partial grids. Theoretical Computer Science 979, 114217 (2023)

7. Chang, G.J., Tong, L.D., Wang, H.T.: Geodetic spectra of graphs. European Journal of Combinatorics 25(3), 383–391 (2004)

8. Chartrand, G., Fink, J.F., Zhang, P.: The hull number of an oriented graph. International Journal of Mathematics and Mathematical Sciences 2003(36), 2265–2275 (2003)

9. Chartrand, G., Zhang, P.: The geodetic number of an oriented graph. European Journal of Combinatorics 21(2), 181–189 (2000)

10. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)

11. Dailly, A., Foucaud, F., Hakanen, A.: Algorithms and hardness for metric dimension on digraphs. In: Paulusma, D., Ries, B. (eds.) Graph-Theoretic Concepts in Computer Science - 49th International Workshop, WG 2023, Fribourg, Switzerland, June 28-30, 2023. Lecture Notes in Computer Science, vol. 14093, pp. 232–245. Springer (2023)

12. Davot, T., Isenmann, L., Thiebaut, J.: On the approximation hardness of geodetic set and its variants. In: Proceedings of the 27th International Computing and Combinatorics Conference, COCOON 2021. Lecture Notes in Computer Science, vol. 13025, pp. 76–88. Springer (2021)

13. Dev, S.R., Dey, S., Foucaud, F., Narayanan, K., Sulochana, L.R.: Monitoring edge-geodetic sets in graphs. Discrete Applied Mathematics 377, 598–610 (2025)

14. Dong, L., Lu, C., Wang, X.: The upper and lower geodetic numbers of graphs. Ars Combinatoria 91, 401–409 (2009)

15. Dourado, M.C., Protti, F., Rautenbach, D., Szwarcfiter, J.L.: Some remarks on the geodetic number of a graph. Discrete Mathematics 310(4), 832–837 (2010)

16. Douthat, A.L., Kong, M.C.: Computing geodetic bases of chordal and split graph. Journal of Combinatorial Mathematics and Combinatorial Computing 22, 67–77 (1996)
17. Ekim, T., Erey, A., Heggernes, P., vant Hof, P., Meister, D.: Computing minimum geodetic sets of proper interval graphs. In: Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012). Lecture Notes in Computer Science, vol. 7256, pp. 279–290. Springer (2012)

18. Farber, M., Jamison, R.E.: Convexity in graphs and hypergraphs. SIAM Journal on Algebraic Discrete Methods **7**(3), 433–444 (1986)

19. Farrugia, A.: Orientable convexity, geodetic and hull numbers in graphs. Discrete Applied Mathematics **148**(3), 256–262 (2005)

20. Foucaud, F., Galby, E., Khazaliya, L., Li, S., Inerney, F.M., Sharma, R., Tale, P.: Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. In: Bringmann, K., Grohe, M., Puppis, G., Svensson, O. (eds.) 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia. LIPIcs, vol. 297, pp. 66:1–66:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2024)

21. Foucaud, F., Galby, E., Khazaliya, L., Li, S., Inerney, F.M., Sharma, R., Tale, P.: Metric dimension and geodetic set parameterized by vertex cover. In: Beyersdorff, O., Pilipczuk, M., Pimentel, E., Nguyen, K.T. (eds.) 42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025, March 4-7, 2025, Jena, Germany. LIPIcs, vol. 327, pp. 33:1–33:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2025)

22. Foucaud, F., Galby, E., Khazaliya, L., Li, S., Inerney, F.M., Sharma, R., Tale, P.: Metric dimension and geodetic set parameterized by vertex cover. In: Beyersdorff, O., Pilipczuk, M., Pimentel, E., Nguyen, K.T. (eds.) 42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025, March 4-7, 2025, Jena, Germany. LIPIcs, vol. 327, pp. 33:1–33:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2025)

23. Foucaud, F., Ghareghani, N., Sharifani, P.: Extremal digraphs for open neighbourhood location-domination and identifying codes. Discrete Applied Mathematics **347**, 62–74 (2024)

24. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)

25. Harary, F., Loukakis, E., Tsouros, C.: The geodetic number of a graph. Mathematical and Computer Modelling **17**(11), 89–95 (1993)

26. Kellerhals, L., Koana, T.: Parameterized complexity of geodetic set. Journal of Graph Algorithms and Applications **26**(4), 401–419 (2022)

27. Lu, C.h.: The geodetic numbers of graphs and digraphs. Science in China Series A: Mathematics **50**(8), 1163–1172 (2007)

28. Mezzini, M.: Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs. Theoretical Computer Science **745**, 63–74 (2018)

29. Pelayo, I.M.: Geodesic Convexity in Graphs. Springer (2013)

30. Tale, P.: Geodetic set on graphs of constant pathwidth and feedback vertex set number. In: Agrawal, A., van Leeuwen, E.J. (eds.) 20th International Symposium on Parameterized and Exact Computation, IPEC 2025, September 17-19, 2025, University of Warsaw, Poland. LIPIcs, vol. to appear. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2025)