pith. sign in

arxiv: 2606.26414 · v1 · pith:WELRAX7Ynew · submitted 2026-06-24 · 💻 cs.DS

Structural parameterizations of Geodetic Set on directed (acyclic) graphs

Beaudou Laurent , Foucaud Florent , Lorieau Lucas , Tale Prafullkumar This is my paper

Pith reviewed 2026-06-26 00:29 UTC · model grok-4.3

classification 💻 cs.DS
keywords directed geodetic setkernelizationparameterized complexitydirected acyclic graphsvertex cover numberreachability diameterW[2]-hardnessETH lower bounds
0
0 comments X

The pith

Directed Geodetic Set on digraphs has a kernel of size 2 to the O of the vertex cover number of the underlying undirected graph.

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

The paper establishes structural parameterizations for Directed Geodetic Set on directed graphs including DAGs. It proves a kernel of size 2 to the O of the vertex cover number of the underlying undirected graph, which yields an algorithm in time 2 to the O of that number squared times a polynomial in n. It also gives a kernel of size (solution size times maximum degree) to the O of the reachability diameter. Hardness results show the problem is W[2]-hard by solution size even on maximum-degree-3 DAGs and para-NP-hard by the combination of maximum degree and reachability diameter on DAGs, establishing that the chosen parameter combinations are necessary.

Core claim

The paper claims that DIRECTED GEODETIC SET admits a kernel of size 2^{O(vcn)} on general digraphs implying a 2^{O(vcn^2)} n^{O(1)} algorithm with an ETH lower bound preventing 2^{o(vcn^2)} n^{O(1)} time, as well as a natural kernel of size (k Δ)^{O(rdiam)} yielding a (k Δ)^{O(rdiam · k)} n^{O(1)} algorithm with its own ETH lower bound. It further establishes that the problem is W[2]-hard parameterized by k even on maximum-degree-3 DAGs and para-NP-hard parameterized by maximum degree and reachability diameter on DAGs.

What carries the argument

The vertex cover number of the underlying undirected graph and the triple of solution size k, maximum degree Δ, and reachability diameter rdiam, each used to bound kernel size via reduction rules that preserve yes/no answers.

If this is right

  • There is an algorithm running in time 2^{O(vcn^2)} · n^{O(1)} on general digraphs.
  • Assuming the ETH, no algorithm runs in time 2^{o(vcn^2)} · n^{O(1)}.
  • There is an algorithm running in time (k Δ)^{O(rdiam · k)} · n^{O(1)} on general digraphs.
  • Assuming the ETH, no algorithm runs in time (k Δ)^{o(rdiam · k)} · n^{O(1)}.
  • The problem remains W[2]-hard parameterized by k even when restricted to maximum-degree-3 DAGs.

Where Pith is reading between the lines

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

  • The same structural parameters could be tested for kernelization on other shortest-path covering problems defined on digraphs.
  • Acyclicity alone does not simplify the parameterized complexity of this covering task, so further restrictions such as planarity or bounded treewidth may be needed for single-parameter FPT results.
  • Practical implementations could first compute a vertex cover of the underlying graph and then apply the kernel rules to reduce large instances before exact solving.

Load-bearing premise

The kernel reduction rules and the ETH-hardness gadgets described in the proofs are correct.

What would settle it

An algorithm that solves Directed Geodetic Set on general digraphs in time 2^{o(vcn^2)} n^{O(1)} would falsify the ETH lower bound claim.

read the original abstract

In DIRECTED GEODETIC SET, we are given a (directed) graph and seek a small solution set $S \subseteq V(G)$ such that every vertex lies on a shortest directed path between two vertices in $S$. It is known that the problem is W[2]-hard when parameterized by the solution size $k$, even on directed acyclic graphs (DAGs). Our first result is a kernel of size $2^{O(vcn)}$ for DIRECTED GEODETIC SET on general digraphs, where $vcn$ denotes the vertex cover number of the underlying (undirected) graph. This implies an algorithm running in time $2^{O(vcn^2)} \cdot n^{O(1)}$. Furthermore, we prove that, assuming the ETH, the problem does not admit an algorithm running in time $2^{o(vcn^2)} \cdot n^{O(1)}$. Next, we show that on general digraphs, DIRECTED GEODETIC SET admits a natural kernel of size $(k\Delta)^{O(rdiam)}$, where $\Delta$ is the maximum degree and $rdiam$ denotes the reachability diameter of the digraph (a natural analogue of diameter of undirected graphs). This yields an algorithm running in time $(k\Delta)^{O(rdiam \cdot k)}\cdot n^{O(1)}$. We further prove that, assuming the ETH, the problem does not admit an algorithm running in time $(k\Delta)^{o(rdiam \cdot k)} \cdot n^{O(1)}$. Finally, we justify the necessity of combining parameters by establishing the following hardness results for DIRECTED GEODETIC SET: - It is W[2]-hard parameterized by $k$, even on digraphs of maximum degree 3. - It is para-NP-hard parameterized by maximum degree and reachability diameter. One can infer that the problem remains W[2]-hard when parameterized by k, even on graphs of reachability diameter 3 from Ara\'ujo and Arraes [DAM 2022]. All our conditional lower bounds and hardness results hold even when the input digraph is restricted to be a DAG.

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 investigates structural parameterizations for the Directed Geodetic Set problem on directed graphs and DAGs. It establishes a kernel of size 2^{O(vcn)} for general digraphs, implying an algorithm in 2^{O(vcn^2)} n^{O(1)} time, with a matching ETH lower bound of no 2^{o(vcn^2)} n^{O(1)} time. It also gives a kernel of size (k Δ)^{O(rdiam)}, with corresponding ETH lower bound. Additionally, it proves W[2]-hardness parameterized by k on maximum-degree-3 DAGs and para-NP-hardness parameterized by maximum degree and reachability diameter, all results holding on DAGs.

Significance. The results are significant for the field of parameterized complexity on directed graphs. The problem is known to be W[2]-hard by solution size k even on DAGs, so identifying parameters like vertex cover number of the underlying graph and combinations of k, Δ, and rdiam that admit kernels is valuable. The paper provides explicit kernel constructions and matching conditional lower bounds, and all hardness results are shown to hold on DAGs. This strengthens the contribution by showing the necessity of combining parameters.

minor comments (1)
  1. [Abstract] Abstract: the inference that W[2]-hardness by k holds on reachability diameter 3 (via the cited Araújo and Arraes result) would benefit from a one-sentence clarification of the parameter relationship used.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the significance of our results on structural parameterizations of Directed Geodetic Set and for recommending minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central results consist of explicit kernelization rules (Sections 3 and 4) for the 2^{O(vcn)} and (kΔ)^{O(rdiam)} kernels, plus ETH-based lower bounds and W[2]/para-NP hardness gadgets that preserve acyclicity. These constructions are self-contained algorithmic reductions that operate directly on the input graph parameters without fitting any quantity to a target output or redefining a result in terms of itself. All hardness claims invoke external standard assumptions (ETH, W[2]-completeness) rather than self-citations or prior author theorems as load-bearing premises. No step matches any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard definitions and background results from graph theory and parameterized complexity; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of directed graphs, shortest directed paths, vertex cover number of the underlying undirected graph, reachability diameter, and the Exponential Time Hypothesis hold.
    These are background assumptions invoked throughout the abstract.

pith-pipeline@v0.9.1-grok · 5959 in / 1422 out tokens · 26302 ms · 2026-06-26T00:29:04.372362+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

13 extracted references · 1 linked inside Pith

  1. [1]

    4 B. Bals, J. Blikstad, D. Dadush, Y. Nazari, and J. Schmidt. Revisiting diameter in directed graphs.arXiv eprint, page 2606.08217, 2026.https://arxiv.org/abs/2606.08217. 5 B. Bergougnoux, O. Defrain, and F. Mc Inerney. Enumerating minimal solution sets for metric graph problems. InWG 2024, volume 14760 ofLecture Notes in Computer Science, pages 50–64,

    Pith/arXiv arXiv 2026

  2. [2]

    Chakraborty, S

    7 D. Chakraborty, S. Das, F. Foucaud, H. Gahlawat, D. Lajou, and B. Roy. Algorithms and complexity for geodetic sets on planar and chordal graphs. InISAAC 2020, volume 181 of LIPIcs, pages 7:1–7:15,

    2020

  3. [3]

    Beaudou, F

    L. Beaudou, F. Foucaud, L. Lorieau, P. Tale 23 8 D. Chakraborty, F. Foucaud, H. Gahlawat, S. K. Ghosh, and B. Roy. Hardness and approxim- ation for the geodetic set problem in some graph classes. InCALDAM 2020, volume 12016 of Lecture Notes in Computer Science, pages 102–115,

    2020

  4. [4]

    Chartrand, J

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

    2003

  5. [5]

    Davot, L

    14 T. Davot, L. Isenmann, and J. Thiebaut. On the approximation hardness of geodetic set and its variants. InCOCOON 2021, volume 13025 ofLecture Notes in Computer Science, pages 76–88,

    2021

  6. [6]

    17 T. Ekim, A. Erey, P. Heggernes, P. van’t Hof, and D. Meister. Computing minimum geodetic sets of proper interval graphs. InLATIN 2012, volume 7256 ofLecture Notes in Computer Science, pages 279–290,

    2012

  7. [7]

    Foucaud, E

    19 F. Foucaud, E. Galby, L. Khazaliya, S. Li, F. Mc Inerney, R. Sharma, and P. Tale. Problems in np can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. InICALP 2024, volume 297 ofLIPIcs, pages 66:1–66:19,

    2024

  8. [8]

    Foucaud, E

    20 F. Foucaud, E. Galby, L. Khazaliya, S. Li, F. Mc Inerney, R. Sharma, and P. Tale. Metric dimension and geodetic set parameterized by vertex cover. InSTACS 2025, volume 327 of LIPIcs, pages 33:1–33:20,

    2025

  9. [9]

    Foucaud, N

    21 F. Foucaud, N. Ghareghani, L. Lorieau, M. Mohammad Noori, R. Parvini Oskuei, and P. Tale. Algorithms and hardness for geodetic set on tree-like digraphs. In N. Misra and A. Pandey, editors,CALDAM 2026, volume 16445 ofLecture Notes in Computer Science, pages 179–193. Springer,

    2026

  10. [10]

    Haeupler, Y

    23 B. Haeupler, Y. Jiang, and T. Saranurak. Reducing shortcut and hopset constructions to shallow graphs. In S. Assadi and E. Rotenberg, editors,SOSA 2026, pages 385–393. SIAM,

    2026

  11. [11]

    25 D. G. Harris and N. S. Narayanaswamy. A faster algorithm for vertex cover parameterized by solution size. InSTACS 2024, volume 289 ofLIPIcs, pages 40:1–40:18,

    2024

  12. [12]

    32 P. Tale. Geodetic set on graphs of constant pathwidth and feedback vertex set number. In A. Agrawal and E. Jan van Leeuwen, editors,IPEC 2025, volume 358 ofLIPIcs, pages 28:1–28:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    2025

  13. [13]

    34 C. Wang, Y. Song, G. Fan, H. Jin, L. Su, F. Zhang, and X. Wang. Optimizing cross- line dispatching for minimum electric bus fleet.IEEE Transactions on Mobile Computing, 22(4):2307–2322, 2023

    2023