Shortcuts and Transitive-Closure Spanners Approximation

We study polynomial-time approximation algorithms for two closely-related problems, namely computing shortcuts and transitive-closure spanners (TC spanners). For a directed unweighted graph $G=(V, E)$ and an integer $d$, a set of edges $E'\subseteq V\times V$ is called a $d$-TC spanner of $G$ if the graph $H:=(V, E')$ has (i) the same transitive-closure as $G$ and (ii) diameter at most $d.$ The set $E''\subseteq V\times V$ is a $d$-shortcut of $G$ if $E\cup E''$ is a $d$-TC spanner of $G$. Our focus is on the following $(α_D, α_S)$-approximation algorithm: given a directed graph $G$ and integers $d$ and $s$ such that $G$ admits a $d$-shortcut (respectively $d$-TC spanner) of size $s$, find a $(dα_D)$-shortcut (resp. $(dα_D)$-TC spanner) with $sα_S$ edges, for as small $α_S$ and $α_D$ as possible. As our main result, we show that, under the Projection Game Conjecture (PGC), there exists a small constant $ε>0$, such that no polynomial-time $(n^ε,n^ε)$-approximation algorithm exists for finding $d$-shortcuts as well as $d$-TC spanners of size $s$. Previously, super-constant lower bounds were known only for $d$-TC spanners with constant $d$ and ${α_D}=1$ [Bhattacharyya, Grigorescu, Jung, Raskhodnikova, Woodruff 2009]. Similar lower bounds for super-constant $d$ were previously known only for a more general case of directed spanners [Elkin, Peleg 2000]. No hardness of approximation result was known for shortcuts prior to our result. As a side contribution, we complement the above with an upper bound of the form $(n^{γ_D}, n^{γ_S})$-approximation which holds for $3γ_D + 2γ_S > 1$ (e.g., $(n^{1/5+o(1)}, n^{1/5+o(1)})$-approximation).