pith. sign in

arxiv: 2603.23193 · v3 · pith:DFDH3HQYnew · submitted 2026-03-24 · 💻 cs.DS · cs.DM

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs

Florent Foucaud , Narges Ghareghani , Lucas Lorieau , Morteza Mohammad-Noori , Rasa Parvini Oskuei , Prafullkumar Tale This is my paper

Pith reviewed 2026-05-15 00:24 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords geodetic setditreesfeedback edge setdirected acyclic graphsNP-hardnesspolynomial-time algorithmparameterized complexityshortest paths
0
0 comments X

The pith

Geodetic Set can be solved in polynomial time on ditrees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the Geodetic Set problem, which seeks a small vertex set S such that every other vertex lies on a shortest directed path between two members of S, admits an efficient algorithm when the input is a ditree. A ditree is a directed graph whose underlying undirected graph is a tree, possibly including some 2-cycles. The same structural restriction yields a fixed-parameter tractable algorithm when the underlying undirected graph is close to a tree, measured by its feedback edge set number, provided there are no 2-cycles. The work also proves that the problem stays NP-hard on directed acyclic graphs even when the underlying undirected graph has constant feedback vertex set number and constant pathwidth, strengthening earlier hardness results that required stronger restrictions on the undirected part.

Core claim

Geodetic Set admits a polynomial-time algorithm on ditrees. On digraphs without 2-cycles whose underlying undirected graph has feedback edge set number fen, the problem can be solved in time 2 to the O(fen) times n to the O(1). The problem remains NP-hard on DAGs even when the underlying undirected graph has constant feedback vertex set number and constant pathwidth.

What carries the argument

Tree-structured dynamic programming that selects vertices to cover all shortest directed paths, exploiting the acyclic or near-tree topology after removing feedback edges.

If this is right

  • Geodetic Set becomes tractable on every directed graph whose skeleton is a tree, including those with bidirectional edges.
  • When the underlying undirected graph has few feedback edges and contains no 2-cycles, the problem is solvable with runtime exponential only in the number of those edges.
  • NP-hardness on DAGs with bounded pathwidth shows that directionality alone does not restore tractability even on very tree-like undirected skeletons.
  • The contrast between the positive ditree result and the DAG hardness isolates 2-cycles and feedback edges as the precise parameters controlling complexity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The results suggest that similar tree DP techniques could be tested on other directed graphs with bounded treewidth after contracting 2-cycles.
  • In applications such as monitoring directed flow networks that are nearly trees, the polynomial algorithm directly supplies an efficient placement method for a minimal covering set.
  • Hardness on constant-pathwidth DAGs indicates that further parameterization by the number of 2-cycles or by directed treewidth might be necessary to regain tractability.

Load-bearing premise

The input digraphs are exactly ditrees or have small feedback edge set, and shortest directed paths can be computed efficiently inside these structures.

What would settle it

A concrete ditree instance on which the claimed polynomial algorithm returns a set that fails to cover some vertex via shortest paths, or a small-fen DAG on which the FPT algorithm exceeds its stated time bound.

Figures

Figures reproduced from arXiv: 2603.23193 by Florent Foucaud, Lucas Lorieau, Morteza Mohammad-Noori, Narges Ghareghani, Prafullkumar Tale, Rasa Parvini Oskuei.

Figure 1
Figure 1. Figure 1: An example of a ditree T and its contracted ditree T c . Proof. Using Lemma 1, we know that every geodetic set of T contain S. So, if we show that S is a geodetic set, it would have minimum size. To prove that, let w ∈ V (T) \ S. We show that there exists a pair (v, u) of vertices of S such that w belongs to the shortest path connecting v to u. Since w is not a sink, there exists a vertex u1 such that wu1 … view at source ↗
Figure 2
Figure 2. Figure 2: In this example digraph D, the red arcs form a hanging ditree. The circled blue subgraph is the core digraph of D. It is composed of three core vertices in black, and five core oriented paths. In particular, the path uvw is a core dipath. path forms a directed path in D, we call it a core dipath [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: 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 δi are represented for only one edge vertex and vertices ass… view at source ↗
Figure 4
Figure 4. Figure 4: Details of the gadget ensuring adjacency of edges and elements. One edge vertex [PITH_FULL_IMAGE:figures/full_fig_p021_4.png] view at source ↗
read the original abstract

In the GEODETIC SET problem, an input is a (di)graph $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 (directed) 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 $\textsf{fen}$, can be solved in time $2^{\mathcal{O}(\textsf{fen})} \cdot n^{\mathcal{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 and constant pathwidth. Our last result significantly strengthens the result of Ara\'ujo 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper claims a polynomial-time algorithm for Geodetic Set on ditrees (digraphs whose underlying undirected graph is a tree, allowing 2-cycles), an FPT algorithm running in 2^{O(fen)} n^{O(1)} time for digraphs without 2-cycles parameterized by feedback edge set number fen, and NP-hardness on DAGs even when the underlying undirected graph has constant feedback vertex set and constant pathwidth, strengthening the 2022 result of Araújo and Arraes.

Significance. If the results hold, they establish a useful algorithmic boundary for Geodetic Set on directed graphs that are tree-like or have small feedback parameters. The polynomial-time result on ditrees via local resolution of 2-cycles in a tree DP is a clean positive contribution, the FPT result extends the structural approach naturally, and the hardness on constant-fvs/pathwidth DAGs tightens the known complexity landscape without relying on larger parameters.

minor comments (1)
  1. The abstract states the FPT runtime but does not explicitly confirm that the algorithm avoids hidden exponential factors in shortest-path computations on the underlying tree structure; a brief sentence in the abstract or introduction would clarify this for readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript and for recommending acceptance. The referee summary accurately reflects the main results: a polynomial-time algorithm for Geodetic Set on ditrees, an FPT algorithm parameterized by feedback edge set on 2-cycle-free digraphs, and NP-hardness on DAGs with constant feedback vertex set and pathwidth.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation chain consists of an independent tree-DP algorithm for ditrees (constant states per 2-cycle, explicit shortest-path checks) followed by a standard FPT reduction for bounded feedback edge set and an explicit NP-hardness reduction on constant-FVS DAGs. None of these steps reduce by construction to fitted parameters, self-citations, or renamed inputs; the cited prior hardness result is from distinct authors and is strengthened rather than presupposed. The central positive result is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper builds on established concepts in graph theory and complexity without introducing new free parameters or entities.

axioms (1)
  • standard math The standard definition of shortest paths in directed graphs and the geodetic set property
    Fundamental to defining the problem and verifying solutions.

pith-pipeline@v0.9.0 · 5626 in / 1119 out tokens · 61482 ms · 2026-05-15T00:24:52.706814+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Discrete Mathematics345(10), 112985 (2022)

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

    work page 2022

  2. [2]

    Discrete Applied Mathematics323, 14–27 (2022)

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

    work page 2022

  3. [3]

    In: Proc

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

    work page 2024

  4. [4]

    In: 31st International Symposium on Algorithms and Compu- tation (ISAAC 2020)

    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 Compu- tation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 181, pp. 7:1–7:15. Schloss Dagstuhl–Leibniz-Zentrum für Informatik,...

    work page 2020

  5. [5]

    In: Proceedings of the 6th International Conference on Algo- rithms and Discrete Applied Mathematics (CALDAM 2020)

    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 Algo- rithms and Discrete Applied Mathematics (CALDAM 2020). Lecture Notes in Computer Science, vol. 12016, pp. 102–115. Springer Interna- tional Publishing,...

    work page 2020

  6. [6]

    Theoretical Computer Sciencel979, 114217 (2023)

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

    work page 2023

  7. [7]

    Eu- ropean Journal of Combinatorics25(3), 383–391 (2004)

    Chang, G.J., Tong, L.D., Wang, H.T.: Geodetic spectra of graphs. Eu- ropean Journal of Combinatorics25(3), 383–391 (2004)

    work page 2004

  8. [8]

    International Journal of Mathematics and Mathematical Sciences 2003(36), 2265–2275 (2003)

    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)

    work page 2003

  9. [9]

    European Journal of combinatorics21(2), 181–189 (2000) 23

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

    work page 2000

  10. [10]

    Springer (2015)

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

    work page 2015

  11. [11]

    In: Paulusma, D., Ries, B

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

    work page 2023

  12. [12]

    In: Proceedings of the 27th Interna- tional Computing and Combinatorics Conference, COCOON 2021

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

    work page 2021

  13. [13]

    Discrete Applied Mathematics377, 598–610 (2025)

    Dev, S.R., Dey, S., Foucaud, F., Narayanan, K., Sulochana, L.R.: Moni- toring edge-geodetic sets in graphs. Discrete Applied Mathematics377, 598–610 (2025)

    work page 2025

  14. [14]

    Ars Combinatoria91, 401–409 (2009)

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

    work page 2009

  15. [15]

    Discrete Mathematics310(4), 832–837 (2010)

    Dourado, M.C., Protti, F., Rautenbach, D., Szwarcfiter, J.L.: Some re- marks on the geodetic number of a graph. Discrete Mathematics310(4), 832–837 (2010)

    work page 2010

  16. [16]

    Journal of Combinatorial Mathematics and Combinatorial Computing22, 67–77 (1996)

    Douthat, A.L., Kong, M.C.: Computing geodetic bases of chordal and split graph. Journal of Combinatorial Mathematics and Combinatorial Computing22, 67–77 (1996)

    work page 1996

  17. [17]

    In: Proceed- ings of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012)

    Ekim, T., Erey, A., Heggernes, P., van’t Hof, P., Meister, D.: Com- puting minimum geodetic sets of proper interval graphs. In: Proceed- ings of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012). Lecture Notes in Computer Science, vol. 7256, pp. 279–

    work page 2012

  18. [18]

    SIAM Journal on Algebraic Discrete Methods7(3), 433–444 (1986)

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

    work page 1986

  19. [19]

    Discrete Applied Mathematics148(3), 256–262 (2005) 24

    Farrugia, A.: Orientable convexity, geodetic and hull numbers in graphs. Discrete Applied Mathematics148(3), 256–262 (2005) 24

    work page 2005

  20. [20]

    In: Bringmann, K., Grohe, M., Puppis, G., Svensson, O

    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 Collo- quium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tal...

    work page 2024

  21. [22]

    In: Beyersdorff, O., Pilipczuk, M., Pimentel, E., Nguyen, K.T

    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 Com- puter Science, STACS 2025, March 4-7, 2025, Jena, Germany. LIPIcs, vol. 327, p...

    work page 2025

  22. [23]

    In: Misra, N., Pandey, A

    Foucaud, F., Ghareghani, N., Lorieau, L., Noori, M.M., Oskuei, R.P., Tale, P.: Algorithms and hardness for geodetic set on tree-like digraphs. In: Misra, N., Pandey, A. (eds.) Algorithms and Discrete Applied Math- ematics - 12th International Conference, CALDAM 2026, Dharwad, In- dia, February 12-14, 2026, Proceedings. pp. 179–193. Lecture Notes in Comput...

    work page 2026

  23. [24]

    Discrete Ap- plied Mathematics347, 62–74 (2024)

    Foucaud, F., Ghareghani, N., Sharifani, P.: Extremal digraphs for open neighbourhood location-domination and identifying codes. Discrete Ap- plied Mathematics347, 62–74 (2024)

    work page 2024

  24. [25]

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

    work page 1979

  25. [26]

    Mathematical and Computer Modelling17(11), 89–95 (1993) 25

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

    work page 1993

  26. [27]

    Journal of Graph Algorithms and Applications26(4), 401–419 (2022)

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

    work page 2022

  27. [28]

    Science in China Series A: Mathematics50(8), 1163–1172 (2007)

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

    work page 2007

  28. [29]

    Theoretical Computer Science745, 63–74 (2018)

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

    work page 2018

  29. [30]

    Springer (2013)

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

    work page 2013

  30. [31]

    In: Agrawal, A., van Leeuwen, E.J

    Tale, P.: Geodetic set on graphs of constant pathwidth and feedback vertex set number. In: Agrawal, A., van Leeuwen, E.J. (eds.) 20th Inter- national 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) 26

    work page 2025