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

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. These problems are important special cases of graph sparsification and arise naturally in the context of reachability problems across computational models.

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). The previous best approximation factor is obtained via a naive combination of known techniques from [Berman, Bhattacharyya, Makarychev, Raskhodnikova, Yaroslavtsev 2011] and [Kogan, Parter 2022], and can provide (n γ D , n γ S )-approximation under the condition 3γD + γS > 1; in particular, for a fixed value γD, our improvement is nearly quadratic.