In the DIRECTED GEODETIC SET problem, given a (directed) graph, we 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ú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.
Blogger's Review: This paper delves into the structural parameterization of the Directed Geodetic Set problem, revealing its complexities and algorithmic limitations under various parameterizations. Through systematic hardness proofs, the authors lay a critical theoretical foundation for future research, particularly highlighting the potential applications in graph theory and algorithm design.