Algorithms and Hardness for Geodetic Set on Tree-Like Digraphs

R S Lekshmi, Narges Ghareghani, Lucas Lorieau, Pouyeh Sharifani, Rasa Parvini Oskuei, Prafullkumar TaleLecture Notes in Computer Science 2026 · DOI · OpenAlex

TL;DR

This paper explores the computational complexity of the Geodetic Set problem on directed graphs that resemble trees. The authors provide a linear-time algorithm for "ditrees" and a fixed-parameter tractable (FPT) algorithm based on the feedback edge set, while simultaneously proving that the problem remains NP-hard on directed acyclic graphs (DAGs) even with a small feedback vertex set.

What Problem Does This Paper Address?

The Geodetic Set problem asks: can we find a subset of vertices $S$ of size $k$ such that every other vertex in the graph lies on a shortest path (a "geodesic") between two vertices in $S$?

Think of this as a network design problem. If you are placing transportation hubs in a city, you want to ensure that every location is "on the way" between at least two hubs to maximize efficiency. While well-studied in undirected graphs, the problem is significantly more complex in directed graphs (digraphs), where paths only go one way.

The authors specifically target "tree-like" digraphs. In graph theory, trees are the simplest structures, but as you add cycles, the complexity usually explodes. This paper maps the boundary: exactly how many cycles can a digraph have before finding a geodetic set becomes computationally "impossible" (NP-hard)?

Methods

The researchers employed a mix of algorithmic design and structural complexity proofs:

  1. Contraction for Ditrees: For ditrees (digraphs whose underlying undirected structure is a tree, but which may contain 2-cycles), the authors developed a "contracted ditree" method. By iteratively merging 2-cycles that don't contain leaves, they reduced the problem to a simpler oriented tree where the solution is primarily composed of "extremal" vertices (sources and sinks).
  2. Base Graph Analysis for FPT: To handle graphs "close to a tree" (parameterized by the feedback edge set number, or fen), they used the concept of a "base graph"—what remains after iteratively removing leaves. They proved that a minimum geodetic set only needs to pick from a small, bounded number of vertices near the "core" of the graph.
  3. Gadget-Based Reduction: To prove NP-hardness for DAGs with a low feedback vertex set number (fvn), they constructed a complex reduction from the 3-Dimensional Matching problem. This involved creating "edge vertices" and "element vertices" connected by paths of specific lengths to encode the matching constraints into the shortest-path structure of the digraph.

Datasets

As a theoretical study in computer science and discrete mathematics, this paper does not use empirical datasets. The results are mathematical proofs and algorithmic designs validated through rigorous logic rather than experimental benchmarks.

Key Insights and Ideas

  • The 2-Cycle Dilemma: A 2-cycle (two vertices pointing at each other) essentially acts like an undirected edge. The authors show that directed graphs with 2-cycles inherit the hardness of undirected graphs, making the presence or absence of these cycles a critical pivot point for complexity.
  • Extremal Vertices are Key: In simple tree-like structures, the "ends" of the graph (sources, sinks, and transitive leaves) are almost always required in a geodetic set. The paper formalizes this, showing that for ditrees, the problem is essentially about identifying these extremal points.
  • Fen vs. Fvn: A major "aha moment" is the distinction between feedback edges and feedback vertices. While having a few extra edges (low fen) makes the problem solvable in $2^{O(fen)} \cdot n^{O(1)}$ time, having a few extra vertices (low fvn) does not help—the problem remains NP-hard even if removing just 12 vertices would turn the graph into a forest.

Key Results

  • Linear-Time Algorithm: The authors provide the first linear-time algorithm for the Geodetic Set problem on ditrees, significantly improving upon previous case-heavy approaches.
  • FPT Tractability: They proved that for oriented graphs (no 2-cycles), the problem is Fixed-Parameter Tractable when parameterized by the feedback edge set number. This algorithm is notably faster than previous versions for undirected graphs because it avoids using heavy Integer Linear Programming (ILP) machinery.
  • Hardness Boundary: They established that Geodetic Set is NP-hard on DAGs even when the underlying undirected graph has a feedback vertex set of size 12. This strengthens previous results that only looked at specific graph classes like bipartite or split graphs.

Limitations and Future Work

The primary limitation is that the FPT algorithm for the feedback edge set (fen) currently only applies to oriented graphs (those without 2-cycles). Because 2-cycles mirror the difficulties of undirected graphs, extending this to general digraphs is a significant challenge that remains open.

Future research directions suggested by the authors include:

  • Exploring directed cactus graphs (dicactii) and outerplanar digraphs.
  • Investigating whether a polynomial kernel exists for the fen parameter (a question that is still open even for undirected graphs).
  • Refining the NP-hardness bound for fvn (can it be proven for a number smaller than 12?).

Summary updated

BibTeX
@inproceedings{lekshmi2026algorithms,
  author = {R S Lekshmi and Narges Ghareghani and Lucas Lorieau and Pouyeh Sharifani and Rasa Parvini Oskuei and Prafullkumar Tale and Rasa Parvini Oskuei},
  title = {{Algorithms and Hardness for Geodetic Set on Tree-Like Digraphs}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2026},
  doi = {10.1007/978-3-032-17156-6\_14},
}

Loading related content...

Figure