Structural parameterizations of Geodetic Set on directed (acyclic) graphs

Laurent Beaudou, Florent Foucaud, Lucas Lorieau, Prafullkumar Tale · 2026

Read Structural parameterizations of Geodetic Set on directed (acyclic) graphs by Laurent Beaudou, Florent Foucaud, Lucas Lorieau, 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-2606-26414.txt.

Introduction

Laurent Beaudou, Florent Foucaud, Lucas Lorieau, and Prafullkumar Tale study the Directed Geodetic Set problem on directed graphs, networks of one-way links. The problem asks for a small set of vertices such that each remaining vertex sits on some shortest one-way path linking two chosen ones. The authors use parameterized complexity, which measures cost growth by one structural feature of the input rather than its whole size.

The problem is already known to be hard when measured by solution size, even on graphs with no directed cycles. The authors prove a kernel, a shrunken equivalent instance, whose size depends on the vertex cover number, which counts how few vertices touch every link. They also show that dependence cannot improve much under a standard assumption. A second kernel uses solution size, maximum degree, and directed diameter, extending earlier work on undirected graphs.

Catalog record

CREATORLaurent Beaudou, Florent Foucaud, Lucas Lorieau, Prafullkumar Tale
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26414

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Structural parameterizations of Geodetic Set on directed (acyclic) graphs Laurent Beaudou, Florent Foucaud, Lucas Lorieau, Prafullkumar Tale Abstract In Directed Geodetic Set , we are given a (directed) graph and seek a small solution set S ⊆ V ⁡ ( G ) S\subseteq V(G) such that every vertex lies on a shortest directed path between two vertices in S 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 𝖶 \mathsf{W} [2]-hard when parameterized by the solution size k 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 ) 2^{O(\textsf{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 ) ⋅ n O ⁡ ( 1 ) 2^{O(\textsf{vcn}^{2})}\cdot n^{O(1)} . Furthermore, we prove that, assuming the 𝖤𝖳𝖧 \mathsf{ETH} , the problem does not admit an algorithm running in time 2 o ⁡ ( vcn 2 ) ⋅ n O ⁡ ( 1 ) 2^{o(\textsf{vcn}^{2})}\cdot 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 - 𝖭𝖯 \mathsf{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 ) (k\Delta)^{O(\textsf{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 ​ Δ ) O ⁡ ( rdiam ⋅ k ) ⋅ n O ⁡ ( 1 ) (k\Delta)^{O(\textsf{rdiam}\cdot k)}\cdot n^{O(1)} . We further prove that, assuming the 𝖤𝖳𝖧 \mathsf{ETH} , the problem does not admit an algorithm running in time ( k ​ Δ ) o ⁡ ( rdiam ⋅ k ) ⋅ n O ⁡ ( 1 ) (k\Delta)^{o(\textsf{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 : 1. It is 𝖶 \mathsf{W} [2]-hard parameterized by k k , even on digraphs of maximum degree 3 3 . 2. It is para - 𝖭𝖯 \mathsf{NP} -hard parameterized by maximum degree and reachability diameter. One can infer that the problem remains 𝖶 \mathsf{W} [2]-hard when parameterized by k k , even on graphs of reachability diameter 3 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. \crefname observationobservationobservations \Crefname observationObservationObservations \crefname myclaimclaimclaims \Crefname myclaimClaimClaims \crefname itemiitemitems \Crefname itemiItemItems \crefname reducrulerulerules \Crefname reducruleRuleRules Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne, Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France and https://perso.isima.fr/~labeaudo/ [email protected]://orcid.org/0000-0003-1959-6855 Université Clermont Auvergne, CNRS, Mines Saint-Étienne, Clermont Auvergne INP, LIMOS, 63000 Clermont-Ferrand, France and https://perso.limos.fr/ffoucaud [email protected]://orcid.org/0000-0001-8198-693XThis author received support from the ANR project GRALMECO (ANR-21-CE48-0004), the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25), the International Research Center “Innovation Transportation and Production Systems” of the I-SITE CAP 20-25, and the CNRS IRL ReLaX. Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne, Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France and https://perso.limos.fr/~lulorieau/ [email protected]://orcid.org/0009-0006-5084-5118This author has received financial support from the CNRS through the MITI interdisciplinary programs. Indian Institute of Science Education and Research Pune, Pune, India and https://pptale.github.io/ [email protected]://orcid.org/0000-0001-9753-0523ARG-MATRICS Grant titled MaPLE (ARGM/2026/0089) ccs Theory of computation \to Design and analysis of algorithms keywords Geodetic Set, Directed Graphs, NP-hardness, Parameterized Complexity † † runningtitle: Parameterizations of Geodetic Set on DAGs † † runningauthor: L. Beaudou, F. Foucaud, L. Lorieau, P. Tale † † copyright: Laurent Beaudou, Florent Foucaud, Lucas Lorieau, Prafullkumar Tale † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction We study Geodetic Set on directed graphs (digraphs for short), which we thus call Directed Geodetic Set . Geodetic Set is a classic network design problem introduced in [ 24 ] based on the notion of convexity for the shortest path metric. See the books [ 3 , 31 ] for more on graph convexity, for which Geodetic Set is a central representative problem. In (Directed) Geodetic Set , one asks for a minimum-size set S of vertices such that each vertex in the input (di)graph is part of some shortest directed path between two vertices of S . (Directed) Geodetic Set models natural network design problems such as selecting hubs in a transportation network [ 8 , 34 ] . It is extensively studied in the literature, and serves as one of the key problems in the area of metric-based algorithmic graph theory, together with its close relative Metric Dimension [ 5 , 19 ] . Directed Geodetic Set is formally stated as follows. Directed Geodetic Set Input: A directed graph D and an integer k . Task: Determine whether there exists a subset S\subseteq V(D) of size at most k such that every vertex in V(D) lies on some directed shortest path between two vertices in S . Geodetic Set was extensively studied on undirected graphs, on which its algorithmic complexity was almost exhaustively determined for standard graph classes [ 1 , 6 , 8 , 9 , 7 , 16 , 17 , 30 ] and under the lenses of parameterized complexity [ 6 , 19 , 20 , 27 , 32 ] , approximation algorithms [ 8 , 14 ] and enumeration complexity [ 5 ] . On digraphs, several studies on Directed Geodetic Set exist regarding upper and lower bounds [ 10 , 11 , 12 , 15 , 18 , 29 ] , see also the book [ 31 , Chapter 6] . However, Directed Geodetic Set was only recently studied on directed graphs from an algorithmic perspective. In [ 2 ] , Directed Geodetic Set was shown to be \mathsf{NP} -hard on DAGs (even when the underlying graph is either split, bipartite or co-bipartite) but polynomial-time solvable on oriented cactus graphs (without 2-cycles). (For a digraph, its underlying graph is the undirected graph obtained by forgetting the orientations of arcs, possibly deleting multiple edges.) In a very recent paper [ 21 ] , Directed Geodetic Set was shown to be \mathsf{NP} -hard even on DAGs whose underlying graph has small feedback vertex set number, but it is polynomial-time solvable on digraphs whose underlying graph is a tree, and it is \mathsf{FPT} on DAGs for the feedback edge set number of the underlying graph. Our goal is to continue the study

Read the complete text