Sparsification Lower Bound for Linear Spanners in Directed Graphs

For $\alpha \ge 1$, $\beta \ge 0$, and a graph $G$, a spanning subgraph $H$ of $G$ is said to be an $(\alpha ,\beta )$-spanner if $\dist(u, v, H) \le \alpha \cdot \dist(u, v, G) + \beta$holdsforanypairofvertices$u$and$v$. These type of spanners, called \emph{linear spanners}, generalizes \emph{additive spanners} and \emph{multiplicative spanners}. Recently, Fomin, Golovach, Lochet, Misra, Saurabh, and Sharma initiated the study of additive and multiplicative spanners for directed graphs (IPEC $2020$). In this article, we continue this line of research and prove that $\text{textsc}DirectedLinearSpanner$ parameterized by the number of vertices $n$ admits no polynomial compression of size $\text{calO}(n^{2-ϵ})$ for any $ϵ>0$ unless $\NP \subseteq \coNP/poly$. We show that similar results hold for \textsc{Directed Additive Spanner} and $\text{textsc}DirectedMultiplicativeSpanner$ problems. This sparsification lower bound holds even when the input is a directed acyclic graph and $\alpha ,\beta$ are \emph{any} computable functions of the distance being approximated.