@online{Chalermsook2502.08032,
TITLE = {Shortcuts and Transitive-Closure Spanners Approximation},
AUTHOR = {Chalermsook, Parinya and Jiang, Yonggang and Mukhopadhyay, Sagnik and Nanongkai, Danupon},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2502.08032},
EPRINT = {2502.08032},
EPRINTTYPE = {arXiv},
YEAR = {2025},
MARGINALMARK = {$\bullet$},
ABSTRACT = {We study polynomial-time approximation algorithms for two closely-related
problems, namely computing shortcuts and transitive-closure spanners (TC
spanner). 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.
As our main result, we show that, under the Projection Game Conjecture (PGC),
there exists a small constant $\epsilon>0$, such that no polynomial-time
$(n^{\epsilon},n^{\epsilon})$-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 ${\alpha_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^{\gamma_D}, n^{\gamma_S})$-approximation which holds for $3\gamma_D +
2\gamma_S > 1$ (e.g., $(n^{1/5+o(1)}, n^{1/5+o(1)})$-approximation).
},
}