An r-missing spanner for a graph G is a sparse subgraph H ⊆ G satisfying that for any u, v pair there is a (possibly approximate) u-v shortest path P in G such that |P \ H| ≤ r. That is, H misses at most r edges from every u-v (approximate) shortest path. [Kogan and Parter, FOCS ’22] introduced the notion of missing spanners as an intermediate step for translating hopset constructions into spanners and distance preservers.

For an n-vertex m-edge digraph G, a D-shortcut is a small set H of directed edges taken from the transitive closure of G, satisfying that the diameter of G ∪ H is at most D. In a sequence of works [Kogan and Parter, SODA 2022 & ICALP 2022] provided shortcut algorithms with improved diameter vs. size tradeoffs. In this paper, we present faster and unified shortcut algorithms for general digraphs. These algorithms also yield improved tradeoffs for the family of bounded-width DAGs. We show:

Hopsets and spanners are fundamental graph structures, playing a key role in shortest path computation, distributed communication, and more. A (near-exact) hopset for a given graph G is a (small) subset of weighted edges H that when added to the graph G reduces the number of hops (edges) of near-exact shortest paths. Spanners and distance preservers, on the other hand, ask for removing many edges from the graph while approximately preserving shortest path distances.We provide a general reduction scheme from graph hopsets to the known metric compression schemes of spanners, emulators and distance preservers. Consequently, we get new and improved upper bound constructions for the latter, as well as, new lower bound results for hopsets. Our main results include:•For n-vertex directed weighted graphs, one can provide $(1+\epsilon)$-approximate distance preservers1for p pairs in $V\times V$ with $O_{\epsilon}(n\cdot p^{2/5}+(np)^{2/3})$ edges. For $p\geq n^{5/4}$, this matches the state-of-the art bounds for reachability preservers by [Abboud and Bodwin, SODA 2018] and the lower bound for exact-distance preservers by [Bodwin, SODA 2016].•For n-vertex undirected weighted graphs, one can provide $(1+\epsilon)$ distance preserves with $\overline{O}_{\epsilon}(n^{1+o(1)}+p\cdot n^{o(1)})$ edges. So far, such bounds could be obtained only for unweighted graphs. Consequently, we also get improved sourcewise spanners [Roditty, Thorup and Zwick, ICALP 2005] and spanners with slack [Chan, Dinitz and Gupta, ESA 2006].•Exact hopsets of linear size admit a worst-case hopbound of $\beta=\Omega(n^{1/3})$. This holds even for undirected weighted graphs, improving upon the $\Omega(n^{1/6})$ lower bound by [Huang and Pettie, SIAM J. Discret. Math 2021]. Interestingly this matches the recent diameter bound achieved for linear directed shortcuts.1I.e., subgraphs that preserve the pairwise distances up to a multiplicative stretch of (1+$\epsilon$).More conceptually, our work makes a significant progress on the tantalizing open problem concerning the formal connection between hopsets and spanners, e.g., as posed by Elkin and Neiman [Bull. EATCS 2020].

For an n-vertex digraph G = (V, E), a shortcut set is a (small) subset of edges H taken from the transitive closure of G that, when added to G guarantees that the diameter of G ∪ H is small. Shortcut sets, introduced by Thorup in 1993, have a wide range of applications in algorithm design, especially in the context of parallel, distributed and dynamic computation on directed graphs. A folklore result in this context shows that every n-vertex digraph admits a shortcut set of linear size (i.e., of O(n) edges) that reduces the diameter to1 . Despite extensive research over the years, the question of whether one can reduce the diameter to with Õ(n) shortcut edges has been left open. We provide the first improved diameter-sparsity tradeoff for this problem, breaking the diameter barrier. Specifically, we show an O(nω)-time randomized algorithm2 for computing a linear shortcut set that reduces the diameter of the digraph to Õ(n1/3). This narrows the gap w.r.t the current diameter lower bound of Ω(n1/6) by [Huang and Pettie, SWAT'18]. Moreover, we show that a diameter of O(n1/2) can in fact be achieved with a sublinear number of O(n3/4) shortcut edges. Formally, letting S(n, D) be the bound on the size of the shortcut set required in order to reduce the diameter of any n-vertex digraph to at most D, our algorithms yield: We also extend our algorithms to provide improved (β, ∊) hopsets for n-vertex weighted directed graphs.

Low congestion shortcuts, introduced by Ghaffari and Haeupler (SODA 2016), provide a unified framework for global optimization problems in the CONGEST model of distributed computing. Roughly speaking, for a given graph G and a collection of vertex-disjoint connected subsets S1,…,Sℓ ⊆V(G), (c,d) low-congestion shortcuts augment each subgraph G[Si] with a subgraph Hi ⊆G such that: (i) each edge appears on at most c subgraphs (congestion bound), and (ii) the diameter of each subgraph G[Si] ∪ Hi is bounded by d (dilation bound). It is desirable to compute shortcuts of small congestion and dilation as these quantities capture the round complexity of many global optimization problems in the CONGEST model. For n-vertex graphs with constant diameter D=O(1), Elkin (STOC 2004) presented an (implicit) shortcuts lower bound with1 c + d + Ωe (n (D-2)/(2D-2)). A nearly matching upper bound, however, was only recently obtained for D ∈ {3,4} by Kitamura et al. (DISC 2019).

Let $G$ be a 2-coloring of a complete graph on $n$ vertices, for sufficiently large $n$. We prove that $G$ contains at least $n^{(\frac{1}{4} - o(1))\log n}$ monochromatic complete subgraphs, thus improving over a lower bound of $n^{0.1576\log n}$ due to Székely [ Combinatorica, 4 (1984), pp. 363--372]. We also present lower bounds concerning the number of monochromatic complete subgraphs within certain ranges of sizes, incomparable in nature to lower bounds previously proved by Conlon [ Combinatorica, 32 (2012), pp. 171--186]. If furthermore one assumes that the largest monochromatic complete subgraph in $G$ is of size $(\frac{1}{2} + o(1))\log n$ (it is a well known open question whether such graphs exist), then for every constant $0 \le c \le \frac{1}{2}$ we determine (up to low order terms) the number of monochromatic complete subgraphs of size $c \log n$. We do so by proving a lower bound that matches (up to low order terms) a previous upper bound of Székely. For example, the number of monochromatic complete subgraphs of size $\frac{1}{2} \log n$ is $n^{\frac{1}{8}(4 - \log e \pm o(1))\log n} \simeq n^{0.32 \log n}$.