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 \((\alpha_D, \alpha_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 \alpha_D)\)-shortcut (resp. \((d \alpha_D)\)-TC spanner) with \(s \alpha_S\) edges, for as small \(\alpha_S\) and \(\alpha_D\) as possible. These problems are important special cases of graph sparsification and arise naturally in the context of reachability problems across computational models.