Structural Parameterizations of Geodetic Set on Directed (Acyclic) Graphs

Abstract

In Directed Geodetic Set, we are given a (directed) graph and seek a small solution set S ⊆ V (G) such that every vertex lies on a shortest directed path between two vertices in S. While most prior work on Directed Geodetic Set has focused on undirected graphs, in this article we study the problem on directed graphs from the perspective of parameterized complexity. It is known that the problem is W[2]-hard when parameterized by the solution size k, even on directed acyclic graphs (DAGs). We investigate structural parameterizations of the problem. 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(vcn2) · n O(1). Furthermore, we prove that, assuming the ETH, the problem does not admit an algorithm running in time 2 o(vcn2) · n O(1). Such a tight quadratic exponential lower bound in the parameter is relatively uncommon in parameterized complexity. These results generalize earlier work on undirected graphs by Foucaud et al. [STACS 2025], and complements a recent result on directed graph by Foucaud et al. [CALDAM 2026], that showed that the problem is para-NP-hard for the pathwidth and feedback vertex set number of the underlying graph. Next, we show that on general digraphs, Directed Geodetic Set admits a natural kernel of size (k∆)O(rdiam) , where ∆ 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∆)O(rdiam·k) · n O(1). We further prove that, assuming the ETH, the problem does not admit an algorithm running in time (k∆)o(rdiam·k) · n O(1). Finally, we justify the necessity of combining parameters by establishing the following hardness results for Directed Geodetic Set: 1. It is W[2]-hard parameterized by k, even on digraphs of maximum degree 3. 2. 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újo and Arraes [DAM 2022]. All our conditional lower bounds and hardness results hold even when the input digraph is restricted to be a DAG.