Algorithms and Hardness for Geodetic Set on Tree-like Digraphs Journal: Theoretical Computer Science
Florent Foucaud, Narges Ghareghani, Lucas Lorieau, Morteza Mohammad-Noori, Rasa Parvini Oskuei, Prafullkumar Tale · 2026
Read Algorithms and Hardness for Geodetic Set on Tree-like Digraphs Journal: Theoretical Computer Science by Florent Foucaud, Narges Ghareghani, Lucas Lorieau, Morteza Mohammad-Noori, Rasa Parvini Oskuei, Prafullkumar Tale (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-23193.txt.
Introduction
Foucaud and co-authors study the geodetic set problem on tree-like directed graphs. A geodetic set covers every other vertex by a shortest path between two chosen vertices. They prove a polynomial-time algorithm for ditrees. Those are digraphs whose base graph is a tree, with two-cycles allowed. For digraphs without two-cycles, run time scales with the feedback edge set size. Hardness remains even in narrow cases, though. The problem stays NP-hard on directed acyclic graphs with constant pathwidth, they show.
Catalog record
| CREATOR | Florent Foucaud, Narges Ghareghani, Lucas Lorieau, Morteza Mohammad-Noori, Rasa Parvini Oskuei, Prafullkumar Tale |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51075 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.23193
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Algorithms and Hardness for Geodetic Set on Tree-like Digraphs Journal: Theoretical Computer Science Florent Foucaud, Narges Ghareghani, Lucas Lorieau, Morteza Mohammad-Noori, Rasa Parvini Oskuei, Prafullkumar Tale Abstract In the Geodetic Set problem, an input is a (di)graph G G and integer k k , and the objective is to decide whether there exists a vertex subset S S of size k k such that any vertex in V ( G ) ∖ S V(G)\setminus S lies on a shortest (directed) path between two vertices in S 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 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 2 -cycles and whose underlying undirected graph has feedback edge set number fen , can be solved in time 2 𝒪 ( fen ) ⋅ n 𝒪 ( 1 ) 2^{\mathcal{O}(\textsf{fen})}\cdot n^{\mathcal{O}(1)} , where n n is the number of vertices. To complement this, we prove that the problem remains 𝖭𝖯 \mathsf{NP} -hard on DAGs (which do not contain 2 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 𝖭𝖯 \mathsf{NP} -hard on DAGs when the underlying undirected graph is either bipartite, cobipartite or split. 1 Introduction Harary, Loukakos, and Tsuros [ 26 ] 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 minimum 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 , 30 ] , 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 [ 26 ] proved that the problem is \mathsf{NP} -hard. See [ 16 ] for the earliest rigorous proof. Later works established that the problem remains \mathsf{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 , 29 ] . To cope with this hardness, the problem has also been investigated through the lenses of parameterized complexity [ 4 , 20 , 22 , 27 , 31 ] and approximation [ 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 , 21 , 31 ] 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 , 28 ] and the book [ 30 , 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 \textrm{Ext}(D) the set of extremal vertices of D (in an oriented graph, this set contains all leaves). An oriented graph is a digraph that do not contains any 2-cycle. The authors remark that in oriented trees, i.e. oriented graphs 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, \textrm{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 , 24 ] . Note that a ditree, contrary to oriented trees, might contain 2-cycles. Our results As our first result, we present a polynomial-time algorithm for ditrees. 1 . 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.