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 [1] based on the notion of convexity for the shortest path metric. See the books [2], [3] 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 [4], [5]. 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 [6], [7]. Directed Geodetic Set is formally stated as follows.

Geodetic Set was extensively studied on undirected graphs, on which its algorithmic complexity was almost exhaustively determined for standard graph classes [4], [8]–[14] and under the lenses of parameterized complexity [7], [9], [15]–[17], approximation algorithms [4], [18] and enumeration complexity [6].

On digraphs, several studies on Directed Geodetic Set exist regarding upper and lower bounds [19]–[24], see also the book [3]. However, Directed Geodetic Set was only recently studied on directed graphs from an algorithmic perspective. In [25], Directed Geodetic Set was shown to be -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 [26], Directed Geodetic Set was shown to be -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 on DAGs for the feedback edge set number of the underlying graph.

Our goal is to continue the study of Directed Geodetic Set and exhibit parameters for which we can obtain algorithms, and prove their optimality under standard complexity assumptions. One natural parameter is the vertex cover number \(\textsf{vcn}\) of the underlying graph of the input digraph. Note that there exists an algorithm for Directed Geodetic Set with respect to \(\textsf{vcn}\) on undirected graphs [15]. Another relevant parameter is the reachability diameter: the maximum directed distance between any pair of vertices in the digraph that are reachable. This parameter was recently introduced in [27] (see also [28]) and earlier under the name maximum finite distance [29] (unlike the classical diameter of a digraph, it is always finite). This metric-based parameter is an analogue of the diameter of a connected undirected graph, and greatly restricts the possible distances in the input digraph.

Our results.

We first extend a result of [15] (for Geodetic Set on undirected graphs) to general directed graphs, by giving a kernel of size \(2^{O(\textsf{vcn})}\), and deriving from it an algorithm. We also prove that, under the Exponential-Time Hypothesis (\(\mathsf{ETH}\)), this algorithm is essentially optimal.

We then give another positive result by showing that if we combine as parameters the solution size, reachability diameter, and maximum degree of the input digraph, we obtain a kernel and an algorithm. Moreover, we show that its running time is essentially optimal under the \(\mathsf{ETH}\).

Unfortunately, there is little hope to generalize the above result by restricting the parameter combination. Indeed, we show in the two next theorems that one cannot omit neither the reachability diameter, nor the solution size, under standard complexity theory assumptions.

Note that Directed Geodetic Set is trivially in for the solution size \(k\), since one can check (in polynomial time), for each vertex subset of size at most \(k\), whether it is a valid solution.

Finally, it is known that Directed Geodetic Set is -complete even on DAGs with reachability diameter 3, and the proof actually implies -hardness for solution size on such DAGs [25]. However, the produced inputs have large maximum degree.

Our results show that Directed Geodetic Set remains hard even on very restrictive classes of digraphs. In that sense, it differs from other metric-based parameters such as Broadcast Domination, which is -hard but for solution size on DAGs and also for solution size and maximum degree on general digraphs [29]. Note that, interestingly, Directed Geodetic Set also differs from the related Metric Dimension problem, which is for solution size plus reachability diameter.¹

Outline of the paper.

We start by a preliminary section in 2. In 3, we study the tractability of Directed Geodetic Set with respect to the parameter vertex cover number. [sec-sol-size-max-deg-mfd,sec-w2-hardness-sol-degree,sec-np-hard-max-deg-mfd] each deals with combinations of solution size, maximum degree and reachability diameter. They contain the proofs of [thm-kernel,thm-W-hard,thm-maxdeg], respectively. We end the paper by presenting some open questions in 7.

2 Preliminaries↩︎

We present general definitions and results that will be used throughout the paper. We refer to the book [30] for terminology and details on parameterized complexity.

A directed graph (digraph for short) \(D\) consists of vertex set \(V(D)\) and arc set \(A(D)\), where each arc is an ordered pair of two different vertices. An arc from vertex \(v\) to vertex \(u\) is denoted by \(vu\), \(v\) is its tail and \(u\) is its head. The underlying undirected graph (or simply underlying graph) of some digraph \(D\) is the graph obtained by removing the orientation of each arc of \(D\). An oriented path of a digraph \(D\) is a subgraph of \(D\) whose underlying graph is a path. A directed path (or dipath) is an oriented path for which all arcs are oriented in the same direction. In the following, except when explicitly stated otherwise, we will simply call a path any directed path. The distance from \(u\) to \(v\) is the length (number of arcs) of a shortest directed path from \(u\) to \(v\) (if \(u=v\), the distance is \(0\)). If no such path from \(u\) to \(v\) exists, then the distance to \(u\) to \(v\) is defined as \(+\infty\). The reachability diameter of a digraph \(D\) is the largest distance from any vertex to another vertex of \(D\) that is not \(+\infty\). A digraph is called strongly connected if any two distinct vertices are connected by two directed paths (one in each direction). A (maximal) strongly connected component of digraph \(D\) is a maximal vertex subset of \(V(D)\) that induces a strongly connected subdigraph of \(D\). The in-neighborhood of vertex \(u\) is denoted by \(N^-(u)\) and its out-neighborhood is denoted by \(N^+(u)\). The in-neighborhood of a subset \(S\) of \(V(D)\) is \(N^-(S)=(\cup_{u\in S}N^-(u))\setminus S\), and similarly the out-neighborhood of \(S\) is defined. A vertex \(x\) is called a source, if \(N^-(x)=\emptyset\), and it is called a sink if \(N^+(x)=\emptyset\). A vertex that is a source or a sink is called extremal. For two vertices \(u\) and \(v\), the set of vertices that lie in some shortest path from \(u\) to \(v\) is denoted by \(I(u,v)\) and for a subset \(S\) of \(V\), the geodetic closure of \(S\), denoted by \(I(S)\), is the set of all vertices which lie in some shortest path between two vertices of \(S\). In other words, \(I(S)=\cup_{u,v \in S} \big(I(u,v)\cup I(v,u)\big)\). We also say that a vertex \(v\) is covered by two vertices \(u\) and \(w\) if \(v\in I(u,w)\). In a path \(P\) from \(u\) to \(v\), vertices \(u\) and \(v\) are called the tail and the head of \(P\), respectively. The vertices of \(P\) which are neither the tail nor the head of \(P\) are called its inner vertices. A directed acyclic graph (DAG for short) is a digraph which does not contain any directed cycle. A vertex \(v\) is transitive if, for every in-neighbor \(u_1\) and out-neighbor \(u_2\) of \(v\), either the arc \(u_1u_2\) exists, or \(u_1=u_2\).² A vertex of a digraph is called a leaf if, in the underlying undirected graph, it has degree 1. Note that any leaf of a digraph is either a sink, a source, or transitive.

We conclude this section with the following lemma.

3 Vertex cover number parameterization↩︎

We restate the main theorem of this section.

3.1 A kernel and an algorithm↩︎

Two vertices of a digraph \(D\) are said to be false twins if they share the same incoming and outgoing open neighborhoods. Note that if two false twins share an arc, then one of them has to admit a loop, which is not possible in the considered setting. A set \(S\) of vertices is called a false twin set, or a set of false twins, if all vertices of \(S\) are pairwise false twins. This notion of twins is central in the kernalization algorithm we present in the following. Indeed, since twins share exactly the same neighborhood, they behave exactly in the same manner with respect to the rest of the graph. We also need to define the following notion.

In particular, if \(S\) is an independent set and its neighborhood is shortcutting, then any vertex in \(S\) is transitive. The following lemma will be useful.

The two following reduction rules remove some vertices of false twin sets. [prop-kernel] shows that this is enough to get a kernel for the parameter vcn.

The next proposition states the existence of the algorithm to be applied on the above kernel. It is the last element necessary for the proof of [thm-vc-algo].

This implies the proof of the first part of [thm-vc-algo], which we state below.

3.2 \(\mathsf{ETH}\)-based lower bound↩︎

In this subsection, we prove the second part of [thm-vc-algo], i.e. that the algorithm obtained in [prop-algo-exp-DGS] is optimal under \(\mathsf{ETH}\)[32]. To this end, we present a reduction from the following variant of 3-SAT defined in [33].

Reduction description

Consider an instance \(\mathcal{I} = (X, Y, Z,\mathcal{C})\) of 3-SAT where \(\mathcal{X} = X\cup Y\cup Z\) is the variable set, with \(|X| = |Y| = |Z| = N\). By adding dummy variables, if necessary, we can assume that \(N = n^2\) for some integer \(n\). Let \(\mathcal{C} = \{C_1, \dots, C_m\}\) be the set of clauses of \(\mathcal{I}\). We create a digraph \(\mathcal{D}=(V, A)\) through the following procedure. The construction is highly symmetric with respect to the partition of \(\mathcal{X}\), so we describe it only for the set \(X\), for the sake of clarity.

• Partition the variables of \(X\) into buckets \(X^1, \dots, X^{n}\), such that each bucket contains \(n\) variables. Without loss of generality, we assume an arbitrary but fixed ordering of buckets and variables inside each bucket. We use the notation \(X^i_j\) to denote \(j\)-th variable of the \(i\)-th bucket. Throughout the construction, we follow the notation that superscript will corresponds the index of the bucket while subscript denotes the vertex index itself.

• For every bucket \(X^i\), add to \(V(\mathcal{D})\) a set \(A^i\) of \(2^{ n}\) vertices corresponding to each possible assignment of the variables of the bucket. Denote those vertices by \(a^i_{p}\) for \(p\in [2^{n}]\).

• For each \(i\in [n]\), add two new vertices \(\alpha_{A ^i}\) and \(\beta_{A^i}\). For each \(i \in [n]\), add the arcs \(\alpha_{A^i}a^i_{p}\) and \(a^i_{p}\beta_{A^i}\) for each \(p\in [2^{n}]\).

• Add vertex sets \(V\), \(R\), \(T\) and \(F\) on \(n\) vertices each. Denote by \(v_i\) (respectively \(r_i\), \(t_i\), \(f_i\)) the vertices of \(V\) (respectively \(R\), \(T\), \(F\)) for \(i\in[n]\). Add the arcs \(a^i_{p}v_i\) for each \(i\in [n]\) and \(p\in[2^{ n}]\). Add also the arcs \(v_i r_{j}\) for all \(i,j\in [n]\) such that \(i\not=j\). Finally, add the arcs \(\alpha_{A_i}v_j\) and \(\alpha^i_{p}r_j\) for all \(i,j\in [n]\) and \(p\in[2^{ n}]\).

• For every \(i \in [n]\) and every \(p \in [2^n]\), connect \(a^i_{p}\) with vertices in \(T\cup F\) such that the connection represents the values of variables set \(X^i\) by the assignment corresponding to \(a^i_{p}\). Formally, the reduction adds the following arcs.

  • If the partial assignment associated to \(a^i_{p}\) is setting variable \(X^i_j\) to true, then we add the arc \(a^i_{p}t_j\). See the green arcs in Figure 2.

  • If the partial assignment associated to \(a^i_{p}\) is setting variable \(X^i_j\) to false, then we add the arc \(a_{i,p}f_j\). See the red arcs in Figure 2.

  Note that \(a^i_{p}\) is connected to exactly \(n\) vertices in \(T \cup F\). More precisely for every \(j \in [n]\), \(a^i_{p}\) is connected to \(t_j\) if and only if it is not connected to \(f_j\), and vice versa.

• Add vertex sets \(U\) and \(W\), both on \(n\) vertices. Denote by \(u_i\) (respectively \(w_i\)) the vertices of the set \(U\) (respectively \(W\)) for \(i\in [ n]\). Add the arcs \(u_iw_i\) and \(r_iw_i\) for all \(i\in [n]\).

• For all sets \(S\) in \(\{T, F\}\), add two vertices \(\alpha_{S}\) and \(\beta_{S}\), as well as a vertex \(\alpha_{U}\). For \(S\in\{T,F,U\}\), add the arcs \(\alpha_Ss_i\) and \(s_i\beta_S\) (when \(\beta_S\) exists) for all \(i\in [n]\), where \(s_i\) designates the vertex of \(S\) with index \(i\).

The previous construction is duplicated twice, to encode variables of \(Y\) and \(Z\) as well. When the naming of vertices of the previously described gadgets is ambiguous, we add a superscript to indicate the variable set it corresponds to. For instance, the vertex \(v_i^Y\) corresponds to the vertex \(v_i\) of the above construction for the variable set \(Y\). For sets \(A^i\) and vertices \(a^i_p\), instead of using a single index as superscript, we give directly the bucket to which it is associated. For instance, vertex \(a^{Z^3}_5\) corresponds to the fifth assignment of bucket \(Z^3\). Additionally, call \(B\) the set of all vertices \(\alpha_S\) and \(\beta_S\) mentioned during the construction.

The end of the construction focuses on encoding the clauses as follows. Recall that \(\mathcal{I}\) is an instance of 3-Partitioned 3-SAT, each clause of \(\mathcal{C}\) contains exactly one variable from \(X\), one from \(Y\) and one from \(Z\).

• Consider a clause \(C_{\ell} \in \mathcal{C}\), and denote literals in \(C_\ell\) (when they exist) by \(X^{i_x}_{j_x}\), \(Y^{i_y}_{j_y}\) and \(Z^{i_z}_{j_z}\) respectively. Add a vertex \(c_{\ell}\) in the graph and add the following arcs.

  • If assigning true(respectively false) to variable \(X^{i_x}_{j_x}\) (when it exists) satisfies the clause \(C_\ell\), then add the arc \(t_{j_x}c_\ell\) (respectively \(f_{j_x}c_\ell\)) and the arc \(c_\ell u_{i_x}\).

  • When they exist, perform a similar operation with variables \(Y^{i_y}_{j_y}\) and \(Z^{i_z}_{j_z}\).

Let \(C\) be the set of all the vertices added with respect to some clause. Note that for every vertex in \(C\), the number of its in-neighbors is equal to the number of its out-neighbors, which is equal to number of literals in it. We will argue that a vertex \(c_{\ell}\) is in a shortest path from a vertex \(a^i_p\) , corresponding to a (partial) assignment, and some sink vertex if and only if the (partial) assignment corresponding to \(a^i_p\) satisfies the clause. We conclude the construction by adding some arcs to prevent ‘unwanted coverage’.

• Add for all \(i\in [n]\) and all \(S,S'\in \{X,Y,Z\}\) the arcs \(\alpha_{A^{S^i}}v_i^{S'}\), \(\alpha_{T^S}u_i^{S'}\) and \(\alpha_{F^S}u_i^{S'}\). These arcs will prevent any coverage from a source vertex associated with the variable set \(S\) to cover clauses with a path going to a sink associated with variable set \(S'\).

• Add for each \(S,S'\in \{X, Y, Z\}\) such that \(S \not = S'\) the arcs \(a^{S^i}_{p}u^{S'}_{j}\) for all \(i, j\in [n]\) and all \(p\in [2^n]\). These arcs will prevent any coverage from a selected vertex associated with the variable set \(S\) to cover clauses with a path going to a sink associated with variable set \(S'\).

This ends the construction of \(\mathcal{D}\). The instance returned by this reduction is \((\mathcal{D},k)\) with \(k=12 n + 15\). 2 is a partial representation of the obtained instance.

Correctness of the reduction

In Lemma 3, we prove that if \(\mathcal{I}\) is satisfiable, then \(\mathcal{D}\) admits a geodetic set of size \(k\). In this section, we present an outline of the proof in the reverse direction.

We first present an informal overview. It is easy to see that all sources and sinks must belong to any geodetic set of \(\mathcal{D}\) (1). We argue that the shortest paths between the sinks and sources cover all the vertices in \(V(\mathcal{D})\), except the vertices in \(C\) and \(\bigcup_{S\in\{X,Y,Z\}}V^S\). For example, consider vertex \(c_{\ell}\) and set \(V\) in Figure 2. We use the simplified notation from the figure to complete the overview.

To cover vertices \(v_1, v_2, v_3, v_4\), and vertex \(c_{\ell}\), any geodetic set must include at least one vertex from the sets \(A^1, A^2, A^3\), and \(A^4\), respectively. The cardinality constraint on the geodetic set ensures that it contains exactly one vertex from each set. This selection naturally corresponds to a valid assignment of the variables in the instance \(\mathcal{I}\). We will argue that this must indeed be a satisfying assignment.

For vertices corresponding to assignments (such as \(a^1_p\) and \(a^3_q\) in Figure 2), their variable assignments are evident from their adjacencies to vertices in \(T\) and \(F\). These two sets relay the assignment information to the clause vertices. Note that both \(a^1_p\) and \(a^3_q\) set the fourth variable in their respective buckets to true. Consider the clause \(c_{\ell}\), which contains the variable \(X^3_4\). To obtain a valid assignment, we must ensure that the shortest path between \(a^3_q\) and some sink vertex covers the vertex \(c_{\ell}\). Moreover, the shortest path between \(a^1_p\) and the sink vertices must not cover \(c_{\ell}\). The relevant sink vertices correspond to the set \(W\).

These conditions are enforced by the vertices in sets \(V\) and \(R\), along with their interconnecting arcs. Consider the two paths \(a^1_p-t_4-c_{\ell}-u_3-w_3\) and \(a^3_q-t_4-c_{\ell}-u_3-w_3\). Note that the first path is not a shortest path because there is a shorter alternative: \(a^1_p-v_1-r_3-w_3\). However, there is no analogous shortcut path \(a^3_q-v_3-r_3-w_3\) because the arc from \(v_3\) to \(r_3\) does not exist. This distinction forms the crux of the proof of correctness.

In the remainder of this section, we formalize this intuition. Before proceeding, we remark that this missing arc and the reliance on these connections to bypass \(V\) for shortest paths critically depends on the fact that clause \(c_{\ell}\) contains at most one literal from the set \(X\).

In the considered construction, we define set \(\mathcal{S}_0\) as the collection of sinks and sources, i.e., \(S_0 := B\cup \bigcup_{S\in \{X,Y,Z\}}W^S\). In the next two observations, we argue that vertices of \(\mathcal{S}^0\) cannot cover vertices in \(C\) and that vertices of \(\bigcup_{S\in\{X,Y,Z\}}V^S\) can only be covered by paths starting at specific vertices not belonging to \(\mathcal{S}^0\).

We also argue that \(\mathcal{D}\) is an acyclic digraph by using another simple observation.

4 Solution size, maximum degree and reachability diameter↩︎

We restate the result proved in this section.

4.1 A kernel and an algorithm↩︎

We now prove the first part of Theorem [thm-kernel]. Let \(D\) be an input digraph to Directed Geodetic Set with maximum degree \(\Delta\) and reachability diameter \(\textsf{rdiam}\). Consider the partition of \(D\) into strongly connected components \(C_1,\ldots,C_t\). We define the digraph \(H\) on vertex set \(C_1,\ldots,C_t\), with an arc from \(C_i\) to \(C_j\) (\(i\neq j\)) if there exists an arc from a vertex in \(C_i\) to a vertex in \(C_j\) in \(D\). Note that \(H\) is a DAG, for otherwise some strongly connected component from the partition would not be maximal. Assume without loss of generality that \(C_1,\ldots,C_p\) (\(1\leq p\leq t\)) are the sources of \(H\).

Let \(v\) be any vertex of \(D\), with \(v\in C_i\) fir some \(i\in [t]\). Then, there exists \(C_j\) with \(1\leq j\leq p\) (that is, \(C_j\) is a source in \(H\)), such that \(C_i\) is reachable from \(C_j\) in \(H\). For any \(i\) with \(1\leq i\leq p\), let \(x_i\) be an arbitrary vertex of the source component \(C_i\) and let \(X=\{x_i \mid 1\leq i\leq p\}\). Then, every vertex in \(D\) is reachable from at least one vertex in \(X\).

Note that the maximum number of vertices reachable from any vertex of \(D\) is at most \(\sum_{i=0}^{\textsf{rdiam}}\Delta^i\leq \Delta^{\textsf{rdiam}+1}\). In any yes-instance of Directed Geodetic Set, we must have \(p\leq k\), as any geodetic set must include some vertex in each strongly connected component that is a source of \(H\). Hence, in a yes-instance, the number of vertices must be at most \(k\Delta^{\textsf{rdiam}+1}\).

The kernelization algorithm is hence straightforward: if \(D\) has more than \(k\Delta^{\textsf{rdiam}+1}\) vertices, we return a trivial no-instance (such as the digraph with \(k+1\) isolated vertices, \(k\) being unchanged); otherwise, we return \((D,k)\) itself.

The algorithm is a simple brute-force algorithm over such a kernel, testing all the possible subsets of size at most \(k\) as a potential geodetic set, and checking in polynomial time whether each of them is indeed a geodetic set or not. This runs in time at most \(\binom{k\Delta^{\textsf{rdiam}+1}}{k}(k \Delta^{\textsf{rdiam}+1})^{O(1)}\) which is in \((k\Delta)^{O(\textsf{rdiam}\cdot k)}\).

4.2 \(\mathsf{ETH}\)-based lower bound↩︎

In this subsection, we prove the second part of Theorem [thm-kernel]. In particular, we show that the simple algorithm obtained by applying brute force to the reduced instance is optimal under the \(\mathsf{ETH}\). To this end, we present a reduction from \(\ell \times \ell\)-Independent Set, which we define formally below and state the corresponding conditional lower bound.

The reduction takes as input an instance \((H,\langle V_1, V_2, \dots, V_\ell\rangle)\) of \(\ell \times \ell\)-Independent Set, runs in polynomial time, and outputs an instance \((D,k)\) of Geodetic Set such that \(k = 3\ell + 1\), the maximum degree of \(D\) satisfies \(\Delta \le \ell^4\), and \(\textsf{rdiam}= 2\).

• Initially, set \(V(D) := V(H)\) and \(A(D) := \emptyset\).

• For each part \(V_i\), introduce three new vertices \(a_i\), \(b_i\), and \(c_i\), and add the arcs \(a_iu\), \(ub_i\), and \(uc_i\) for every \(u \in V_i\).

• For every pair \(i \neq j \in [\ell]\), construct a set \(F_{i,j}\) as follows. For every edge \(uv \in E(H)\) with \(u \in V_i\) and \(v \in V_j\), add a corresponding vertex \(f_{uv}\) to \(F_{i,j}\).

• For every \(i \in [\ell]\) and every vertex \(w \in V_i\), add an arc \(wf_{uv}\) for every vertex \(f_{uv} \in F_{i,j}\) with \(j \in [\ell] \setminus \{i\}\), provided that \(w \notin \{u,v\}\). Equivalently, the arc \(wf_{uv}\) is added if and only if the edge \(uv\) is not incident to \(w\) in \(H\).

• Introduce a special vertex \(d\). For every \(i \neq j \in [\ell]\), add the arc \(f_{uv}d\) for every vertex \(f_{uv} \in F_{i,j}\). Moreover, for every \(i \in [\ell]\), add the arcs \(a_id\) and \(c_id\).

This completes the construction of the digraph \(D\). The reduction outputs the instance \((D, k)\) with \(k = 3\ell + 1\) of Geodetic Set. In the following lemma, we prove the correctness of the reduction.

The conditional lower bound mentioned in Theorem [thm-kernel] follows from [prop-eth-ind-set,lemma-ind-set-geodetic-eth].

5 \(\W[2]\)-hardness for solution size on subcubic DAGs↩︎

We restate the result proved in this section.

The proof is adapted from the reduction from Set Cover to Directed Geodetic Set in [25], that implies its -hardness and \(\W[2]\)-hardness on DAGs (of unbounded maximum degree). In fact, we find it notationally cleaner to first revisit the proof from Set Cover to Directed Geodetic Set mentioned in [25]. Then, we modify the reduced instance to ensure that it has bounded maximum degree. Given an instance \((U,\mathcal{F},k)\) of Set Cover with \(U=\{1,\ldots,n\}\), and \(\mathcal{F}=\{F_1,\ldots,F_m\},\) we construct a directed acyclic graph \(D\) as follows. The vertex set of \(D\) is \(V(D) = X \cup Y \cup \{s,t_1,t_2\}\), where \(X=\{f_1,\ldots,f_m\}\) and \(Y=\{u_1,\ldots,u_n\}\). The arc set \(A(D)\) contains the following arcs: \((i)\) For every set \(F_i \in\mathcal{F}\) and element \(j \in U\), if \(j \in F_i\) then add the arc \((f_i,u_j)\in A(D)\). \((ii)\) For each set vertex \(f_i \in X\), add arcs \(sf_i\), and \(f_it_1\). \((iii)\) For each vertex \(u_j \in Y\), add the arc \(u_jt_2\). \((iv)\) Finally add a single arc \(st_2\in A(D)\). It is easy to see that \(D\) is a DAG, since we orient all arcs consistently from \(\{s\}\) towards the sinks \(\{t_1, t_2\}\).

We construct a new digraph \(D'\) from the digraph \(D\) obtained in the last reduction by locally replacing high-degree vertices with directed binary trees. The transformation ensures: \(V(D) \subseteq V(D')\), \(D'\) is a DAG, the maximum degree in \(D'\) is \(3\), and finally \((D,k+3)\) is a yes-instance of Geodetic Set if and only if \((D',k+3)\) is.

Let \(\Delta=\Delta(D)\) denote the maximum total degree of \(D\). We define a binary tree of height exactly \(\lceil\log \Delta\rceil\) as a rooted tree in which every internal vertex has at most two children, every root-to-leaf path has length exactly \(\lceil\log \Delta\rceil\), and the tree has exactly \(L\le \Delta\) leaves. All internal vertices have total degree at most 3.

• Delete the vertex \(t_1\) from \(D\) (it will be reintroduced later on).

• Construct an outgoing binary tree \(T_s^{\mathrm{out}}\) with \(|N^+(s)|\) leaves, whose arcs are oriented away from its root \(s^+\). For every original arc \(sf_i\) where \(f_i\in X\), delete it and instead connect the corresponding leaf of \(T_s^{\mathrm{out}}\) to \(f_i\). Add the arc \(ss^+\).

• For each \(f_i\in X\), construct an outgoing binary tree \(T_{f_i}^{\mathrm{out}}\) with \(|N^+(f_i)|\) leaves, oriented away from its root \(f_i^{+}\). For every original arc \(f_iu_j\), delete it. Similarly, for each \(u_j\in Y\), construct an incoming binary tree \(T_{u_j}^{\mathrm{in}}\) with \(|N^-(u_j)|\) leaves, whose arcs are oriented toward its root \(u_j^{-}\).

  For every original arc \(f_iu_j\) of \(D\), connect one leaf of \(T_{f_i}^{\mathrm{out}}\) to one distinct leaf of \(T_{u_j}^{\mathrm{in}}\). This replaces all arcs from \(X\) to \(Y\).

• Construct an incoming binary tree \(T_{t_2}^{\mathrm{in}}\) whose arcs are oriented toward its root \(t_2^{-}\). Attach every leaf of \(T_{u_j}^{\mathrm{out}}\) corresponding to an original arc \(u_jt_2\) to a distinct leaf of \(T_{t_2}^{\mathrm{in}}\). Add the arc \(t_2^{-}t_2\).

• Reintroduce vertex \(t_1\) by adding it to the graph. For every \(u_j\in Y\), add the arc \(u_j^{-}t_1\). Construct an incoming binary tree \(T_{t_1}^{\mathrm{in}}\) with leaves corresponding to all arcs \((u_j^{-},t_1)\), and orient all arcs toward its root \(t_1^{-}\). Replace each arc \(u_j^{-}t_1\) by an arc from \(u_j^{-}\) to a distinct leaf of \(T_{t_1}^{\mathrm{in}}\), and add the arc \(t_1^{-}t_1\).

Let \(D'\) be the resulting digraph. We remark that arc \(st_2\) has not been disturbed by the above modifications and it is present in \(D'\). All added gadgets are directed trees with consistent orientation. Since the original graph is a DAG, replacing arcs by tree paths cannot create a directed cycle. Hence \(D'\) is a DAG. Finally, every internal node of every tree has total degree at most 3, and each original vertex is incident to at most one incoming and two outgoing arcs and hence the maximum degree of \(D\) is at most \(3\). We are now ready to prove Theorem [thm-W-hard].

6 -hardness for subcubic DAGs with small reachability diameter↩︎

We restate the result proved in this section.

We prove the theorem by reducing from a variant of 3-SAT where the number of occurrences of a variable in clauses is at most three.

We consider an instance \(\mathcal{I} = (X,C)\) of 3-Occ 3-SAT and construct a digraph \(D =(V,A)\) based on \(\mathcal{I}\). Without loss of generality, we order the set of variables \(X\) such that \(X=\{x_1, \dots, x_n\}\). We also order the set of clauses \(C\) such that \(C = \{c_1, \dots, c_m\}\).

Before describing the structure of \(D\), we introduce link gadgets that will be used throughout the construction of \(D\) to ensure the maximum degree of \(D\) remains low. Those gadgets are similar to the binary trees used in 5. A simple link gadget \(L\) is a binary tree of height exactly \(2\) with three leaves. Denote its vertex set as \(V^L = \{m_1^L, m^L_2, m^L_3\}\cup \{a^L_1, a^L_2\}\cup \{u^L\}\), where the vertex \(u^L\) is the root, the three vertices \(m_i^L\) for \(1\leq i\leq 3\) the leaves, and vertices \(a^L_1\) and \(a^L_2\) are the inner vertices of said binary tree. Furthermore, the orientation of the arcs is either from \(u^L\) to vertices \(m_i^L\) (in this case, the linking gadget is said to be dividing) or from vertices \(m_i^L\) to \(u^L\) (and the linking gadget is said to be grouping).

Finally, we also define an extended version of both types of gadgets. To do so, subdivide the arcs respectively from \(a_1^L\) and \(a_2^L\) to \(u^L\) by respectively adding the vertices \(b_1^L\) and \(b_2^L\) and orient the new arcs in the direction of the subdivided arcs. To distinguish the extended version of the gadgets from the original one, we will denote the latter with a superscript bar, so that the notation \(L\) corresponds to a simple linking gadget, while \(\bar L\) corresponds to an extended one. 4 depicts one simple and one extended link gadget, and introduces a compact representation for both types of link gadgets.

Variable gadgets.

For each variable \(x\in X\), add in \(V\) a set \(V^x\) of vertices such that \(V^x = \{s^x, t_1^x, t_2^x, a^x\}\cup\{\mu^x_i\mid \mu\in \{\nu, \pi\},\;i\in[7]\}\). We also add:

• three arcs from \(s^x\) respectively to \(\pi^x_0\), \(\nu^x_0\) and \(t_2^x\);

• for all \(\mu\in \{\pi, \nu\}\) and all \(i\in[0,6]\), an arc from \(\mu^x_i\) to \(\mu^x_{i+1}\);

• for all \(\mu\in \{\pi, \nu\}\), two arcs from \(\mu_7^x\) respectively to \(t_1^x\) and \(a^x\);

• an arc from \(a^x\) to \(t_2^x\).

Clause gadgets.

For any clause \(c\in C\), add one extended grouping gadget \(\bar L^c\) and a dividing gadget \(L^c\), along with two vertices \(t_1^c\) and \(t_2^c\). Call \(V^c\) the set of vertices of a clause gadget, such that \(V^c = V^{L^c}\cup V^{\bar{L^c}}\cup\{t_1^c, t_2^c\}\). Add also the following arcs:

• two arcs respectively from \(b_1^{\bar L^c}\) and \(b_2^{\bar L^c}\) to \(t_1^c\).

• an arc from \(u^{\bar L^c}\) to \(u^{L^c}\).

• three arcs respectively from \(m^{L^c}_1,\;m^{L^c}_2\) and \(m^{L^c}_3\) to \(t^c_2\).

Linking variables and clauses.

Consider a variable \(x\in X\) and denote by \(C(x)\) the set of clauses \(\{c_i, c_j, c_k\}\) such that \(x\) occurs in \(c_i,\; c_j\) and \(c_k\), and \(i\leq j\leq k\). Note that the set \(C(x)\) can also be of size 1 or 2, in which case we respectively consider that \(i=j=k\) and \(j=k\). Define also \(C_0(x) = c_i\), \(C_1(x) = c_j\) and \(C_2(x) = c_k\). We consider similar notions for a clause \(c\in C\), so that the set of variables appearing in \(c\) is denoted by \(X(c) = \{x_i, x_j,x_k\}\) with \(i\leq j\leq k\). We also define \(X_0(c) = x_i\), \(X_1(c) = x_j\) and \(X_2(c) = x_k\). We will add to \(A\) some arcs by following the next procedure:

• for \(1\leq p\leq |C(x)|\):

  • Let \(c = C_p(x)\) and \(q\) be the smallest integer such that \(X_q(c) = x\),

  • if \(x\) appears as a positive literal in \(c\), then add the arcs from \(\pi^x_{p}\) to \(m^{L^c}_q\) and from \(\pi^x_{3+p}\) to \(m^{\bar L^c}_q\), otherwise add the arc from \(\nu^x_{p}\) to \(m^{L^c}_q\) and from \(\nu^x_{3+p}\) to \(m^{\bar L^c}_q\).

This concludes the construction of \(D\). A partial representation of \(D\) displaying the gadgets corresponding to a variable \(x\) appearing in a clause \(c\) can be found in 5. We first prove that the reachability diameter and the feedback vertex number of the obtained graph are constant.

Recall 1 which states that any extremal vertex of a given digraph is a part of any geodetic sets of said digraph. Consider the set \(V_0\) of extremal vertices of \(D\). Then we have \(V_0 = \{s^x, t^x_1, t^x_2\mid x\in X\}\cup\{t^c_1, t^c_2\mid c\in C\}\), and the only sources of \(D\) are the vertices \(s^x\) for \(x\in X\). [prop-delta43mfd-extremalcover] describes which vertices of \(D\) are not covered by \(V_0\).

We now prove the next two main lemmas of this section, that will justify the soundness of the reduction. We then end the section by proving [thm-maxdeg].

7 Conclusion and further work↩︎

In this work, we studied some structural parameters that, combined together, give an optimal (under \(\mathsf{ETH}\)) algorithm to solve Directed Geodetic Set. In particular, we considered the influence of the maximum degree of a digraph, which can be seen as some measure of sparsity. The parameterized complexity of Directed Geodetic Set has been studied recently for other sparse digraphs, namely “tree-like” directed (acyclic) graphs [26]. A natural extension of this work would be to consider the parameterized complexity of Directed Geodetic Set with respect to other parameters capturing some notion of sparsity, or other classes of digraphs that are sparse. One could also study the existence of other kernels for Directed Geodetic Set on directed graphs, especially for cases where the problem is known to be . In particular, to the best of our knowledge, no polynomial size kernel for Directed Geodetic Set on digraphs is known.

References↩︎

---

1. Indeed, in this problem, every vertex needs a distinct distance-vector to the solution vertex set of size \(k\) (where the distance between two vertices may be infinite), and there can be at most \(k+(\textsf{rdiam}+1)^k\) such distinct vectors in a YES-instance), yielding a trivial kernel of this size.↩︎

2. Note that the latter condition was not present in the definition from [25], since the authors only considered digraphs without 2-cycles.↩︎