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(vcn²) ⋅ n^O(1). Furthermore, we prove that, assuming the ETH, the problem does not admit an algorithm running in time 2^o(vcn²) ⋅ 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.

We prove that the recognition of exact cubes of trees can be done in polynomial time. More precisely, the exact distance power of a graph is a refinement of the more usual notion of graph power. Given a graph G and a positive integer p , the exact distance p th power of G is the graph G #p on the same vertex set where two vertices are adjacent if their distance is exactly p in G . Recently Bai et al. [Y. Bai, P. P. Cortés, R. Naserasr and D. A. Quiroz. Characterizing and recognizing exact-distance squares of graphs. Discrete Mathematics 347(8). 2024] proved that the recognition of exact squares of trees is polynomially tractable. In order to extend this result to exact cubes of trees, we first test whether there is a caterpillar as an exact cubic root and, if not, proceed with a general tree. Both algorithms rely on the observation that the knowledge of a fixed number of vertices is roughly enough to deduce the whole structure of the tree we aim for.

International audience

The metric dimension of a graph is the minimum size of a set of vertices such that each vertex is uniquely determined by the distances to the vertices of that set. Our aim is to upper-bound the order $n$ of a graph in terms of its diameter $d$ and metric dimension $k$. In general, the bound $n\leq d^k+k$ is known to hold. We prove a bound of the form $n=\mathcal{O}(kd^2)$ for trees and outerplanar graphs (for trees we determine the best possible bound and the corresponding extremal examples). More generally, for graphs having a tree decomposition of width $w$ and length $\ell$, we obtain a bound of the form $n=\mathcal{O}(kd^2(2\ell+1)^{3w+1})$. This implies in particular that $n=\mathcal{O}(kd^{\mathcal{O}(1)})$ for graphs of constant treewidth and $n=\mathcal{O}(f(k)d^2)$ for chordal graphs, where $f$ is a doubly exponential function. Using the notion of distance-VC dimension (introduced in 2014 by Bousquet and Thomassé) as a tool, we prove the bounds $n\leq (dk+1)^{t-1}+1$ for $K_t$-minor-free graphs and $n\leq (dk+1)^{d(3\cdot 2^{r}+2)}+1$ for graphs of rankwidth at most $r$.

Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollak [Bell System Tech. J., 50 (1971), pp. 2495–2519] and Djoković [J. Combinatorial Theory Ser. B, 14 (1973), pp. 263–267]. Several papers followed with various characterizations of partial cubes. In this paper, it is proven that a subdivision of a complete graph of order n ($n \geq 4$) is a partial cube if and only if it is isomorphic to $S(K_n)$ or there exist $n-1$ nonsubdivided edges of $K_n$ adjacent to a common vertex in the subdivision and the other edges of $K_n$ are subdivided an odd number of times. As a corollary, we build partial cubes with arbitrary graph as a minor.