We study multiplicative graph spanners in the $f$-degree fault tolerant ($f$-DFT) model, in which the spanner must approximately preserve distances even after any subset of edges of maximum degree $f$ temporarily "fails" and is removed from the graph. We prove that there are $n$-node lower bound graphs for which any $f$-DFT $(2k-1)$-stretch spanner $H$ must have size $$|E(H)| \ge Ω\left( f^{1-1/k} n^{1+1/k}\right).$$ This matches a lower bound that was previously only known to hold conditionally, under the 1963 girth conjecture of Erdős. It also matches the current upper bounds, up to a factor of $\texttt{exp}(k)$. Our proof is an analysis of the so-called Wenger graphs (J. Comb. Theory 1991), via their recent reinterpretation by Szabó and by Conlon (Am. Math. Monthly 2021).

There has recently been significant interest in fault tolerant spanners, which are spanners that still maintain their stretch guarantees after some nodes or edges fail. This work has culminated in an almost complete understanding of the three-way tradeoff between stretch, sparsity, and number of faults tolerated. However, despite some progress in metric settings, there have been no results to date on the tradeoff in general graphs between stretch, lightness, and number of faults tolerated. We initiate the study of light edge fault tolerant (EFT) graph spanners, obtaining the first such results. First, we observe that lightness can be unbounded if we use the traditional definition (normalizing by the MST). We then argue that a natural definition of fault-tolerant lightness is to instead normalize by a min-weight fault tolerant connectivity preserver; essentially, a fault-tolerant version of the MST. However, even with this, we show that it is still not generally possible to construct $f$-EFT spanners whose weight compares reasonably to the weight of a min-weight $f$-EFT connectivity preserver. In light of this lower bound, it is natural to then consider bicriteria notions of lightness, where we compare the weight of an $f$-EFT spanner to a min-weight $(f' > f)$-EFT connectivity preserver. The most interesting question is to determine the minimum value of $f'$ that allows for reasonable lightness upper bounds. Our main result is a precise answer to this question: $f' = 2f$. In particular, we show that the lightness can be untenably large (roughly $n/k$ for a $k$-spanner) if one normalizes by the min-weight $(2f-1)$-EFT connectivity preserver. But if one normalizes by the min-weight $2f$-EFT connectivity preserver, then we show that the lightness is bounded by just $O(f^{1/2})$ times the non-fault tolerant lightness (roughly $n^{1/k}$, for a $(1+ε)(2k-1)$-spanner).

A recent upper bound by Le and Solomon [STOC ’23] has established that every n-node graph has a (1 + ε )(2k — 1)-spanner with lightness O {ε-x n 1/k). This bound is optimal up to its dependence on ε; the remaining open problem is whether this dependence can be improved or perhaps even removed entirely.

A reachability preserver is a basic kind of graph sparsifier, which preserves the reachability relation of an n-node directed input graph G among a set of given demand pairs P of size | P| = p. We give constructions of sparse reachability preservers in the online setting, where G is given on input, the demand pairs (s,t ) ∈ P arrive one at a time, and we must irrevocably add edges to a preserver H to ensure reachability for the pair (s,t ) before we can see the next demand pair. Our main results are:

The restoration lemma is a classic result by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt [PODC ’01], which describes how the structure of shortest paths in a graph can change when some edges in the graph fail. Their work shows that, after one edge failure, any replacement shortest path avoiding this failing edge can be partitioned into two pre-failure shortest paths. More generally, this implies an additive tradeoff between fault tolerance and subpath count: for any f, k, we can partition any f-edge-failure replacement shortest path into k + 1 subpaths which are each an (f — k )-edge-failure replacement shortest path. This generalized version of the result has found applications in routing, graph algorithms, fault tolerant network design, and more.

The hereditary discrepancy of a set system is a certain quantitative measure of the pseudorandom properties of the system. Roughly, hereditary discrepancy measures how well one can $2$-color the elements of the system so that each set contains approximately the same number of elements of each color. Hereditary discrepancy has well-studied applications e.g. in communication complexity and derandomization. More recently, the hereditary discrepancy of set systems of shortest paths has found applications in differential privacy [Chen et al.~SODA 23]. The contribution of this paper is to improve the upper and lower bounds on the hereditary discrepancy of set systems of unique shortest paths in graphs. In particular, we show that any system of unique shortest paths in an undirected weighted graph has hereditary discrepancy $\widetilde{O}(n^{1/4})$, and we construct lower bound examples demonstrating that this bound is tight up to hidden $\text{polylog } n$ factors. Our lower bounds apply even in the planar and bipartite settings, and they improve on a previous lower bound of $Ω(n^{1/6})$ obtained by applying the trace bound of Chazelle and Lvov [SoCG'00] to a classical point-line system of Erdős. As applications, we improve the lower bound on the additive error for differentially-private all pairs shortest distances from $Ω(n^{1/6})$ [Chen et al.~SODA 23] to $Ω(n^{1/4})$, and we improve the lower bound on additive error for the differentially-private all sets range queries problem to $Ω(n^{1/4})$, which is tight up to hidden $\text{polylog } n$ factors [Deng et al.~WADS 23].

We construct $n$-node graphs on which any $O(n)$-size spanner has additive error at least $+Ω(n^{3/17})$, improving on the previous best lower bound of $Ω(n^{1/7})$ [Bodwin-Hoppenworth FOCS '22]. Our construction completes the first two steps of a particular three-step research program, introduced in prior work and overviewed here, aimed at producing tight bounds for the problem by aligning aspects of the upper and lower bound constructions. More specifically, we develop techniques that enable the use of inner graphs in the lower bound framework whose technical properties are provably tight with the corresponding assumptions made in the upper bounds. As an additional application of our techniques, we improve the corresponding lower bound for $O(n)$-size additive emulators to $+Ω(n^{1/14})$.

The aspect ratio of a (positively) weighted graph $G$ is the ratio of its maximum edge weight to its minimum edge weight. Aspect ratio commonly arises as a complexity measure in graph algorithms, especially related to the computation of shortest paths. Popular paradigms are to interpolate between the settings of weighted and unweighted input graphs by incurring a dependence on aspect ratio, or by simply restricting attention to input graphs of low aspect ratio. This paper studies the effects of these paradigms, investigating whether graphs of low aspect ratio have more structured shortest paths than graphs in general. In particular, we raise the question of whether one can generally take a graph of large aspect ratio and reweight its edges, to obtain a graph with bounded aspect ratio while preserving the structure of its shortest paths. Our findings are: - Every weighted DAG on $n$ nodes has a shortest-paths preserving graph of aspect ratio $O(n)$. A simple lower bound shows that this is tight. - The previous result does not extend to general directed or undirected graphs; in fact, the answer turns out to be exponential in these settings. In particular, we construct directed and undirected $n$-node graphs for which any shortest-paths preserving graph has aspect ratio $2^{Ω(n)}$. We also consider the approximate version of this problem, where the goal is for shortest paths in $H$ to correspond to approximate shortest paths in $G$. We show that our exponential lower bounds extend even to this setting. We also show that in a closely related model, where approximate shortest paths in $H$ must also correspond to approximate shortest paths in $G$, even DAGs require exponential aspect ratio.

Suppose we are given an $n$-node, $m$-edge input graph $G$, and the goal is to compute a spanning subgraph $H$ on $O(n)$ edges. This can be achieved in linear $O(m + n)$ time via breadth-first search. But can we hope for \emph{sublinear} runtime in some range of parameters? If the goal is to return $H$ as an adjacency list, there are simple lower bounds showing that $Ω(m + n)$ runtime is necessary. If the goal is to return $H$ as an adjacency matrix, then we need $Ω(n^2)$ time just to write down the entries of the output matrix. However, we show that neither of these lower bounds still apply if instead the goal is to return $H$ as an \emph{implicit} adjacency matrix, which we call an \emph{adjacency oracle}. An adjacency oracle is a data structure that gives a user the illusion that an adjacency matrix has been computed: it accepts edge queries $(u, v)$, and it returns in near-constant time a bit indicating whether $(u, v) \in E(H)$. Our main result is that one can construct an adjacency oracle for a spanning subgraph on at most $(1+\varepsilon)n$ edges, in $\tilde{O}(n \varepsilon^{-1})$ time, and that this construction time is near-optimal. Additional results include constructions of adjacency oracles for $k$-connectivity certificates and spanners, which are similarly sublinear on dense-enough input graphs. Our adjacency oracles are closely related to Local Computation Algorithms (LCAs) for graph sparsifiers; they can be viewed as LCAs with some computation moved to a preprocessing step, in order to speed up queries. Our oracles imply the first Local algorithm for computing sparse spanning subgraphs of general input graphs in $\tilde{O}(n)$ query time, which works by constructing our adjacency oracle, querying it once, and then throwing the rest of the oracle away. This addresses an open problem of Rubinfeld [CSR '17].

We study a new and stronger notion of fault-tolerant graph structures whose size bounds depend on the degree of the failing edge set, rather than the total number of faults. For a subset of faulty edges F ⊆ G, the faulty-degree deg(F) is the largest number of faults in F incident to any given vertex. For example, a matching F has deg(F) = 1 while |F| might be as large as n/2.

Abstract. We define and study reachability preservers, a graph-theoretic primitive that has been implicit in prior work on network design. Given a directed graph [Formula: see text] and a set of demand pairs [Formula: see text], a reachability preserver is a sparse subgraph [Formula: see text] that preserves reachability between all demand pairs Our first contribution is a series of extremal bounds on the size of reachability preservers. Our main result states that, for an [Formula: see text]-node graph and demand pairs of the form [Formula: see text] for a small node subset [Formula: see text], there is always a reachability preserver on [Formula: see text] edges. We additionally give a lower bound construction demonstrating that this upper bound characterizes the settings in which [Formula: see text] size reachability preservers are generally possible, in a large range of parameters. The second contribution of this paper is a new connection between extremal graph sparsification results and classical Steiner Network Design problems. Surprisingly, prior to this work, the osmosis of techniques between these two fields had been superficial. This allows us to improve the state of the art approximation algorithms for the most basic Steiner-type problem in directed graphs from the [Formula: see text] of Chlamtáč et al. [ Approximating spanners and directed steiner forest: Upper and lower bounds, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 534–553] to [Formula: see text].

For a graph G, a D-diameter-reducing exact hopset is a small set of additional edges H that, when added to G, maintains its graph metric but guarantees that all node pairs have a shortest path in $G \cup H$ using at most D edges. A shortcut set is the analogous concept for reachability rather than distances. These objects have been studied since the early ’90s, due to applications in parallel, distributed, dynamic, and streaming graph algorithms.For most of their history, the state-of-the-art construction for either object was a simple folklore algorithm, based on randomly sampling nodes to hit long paths in the graph. However, recent breakthroughs of Kogan and Parter [SODA ’22] and Bernstein and Wein [SODA ’23] have finally improved over the folklore algorithm for shortcut sets and for $(1+\varepsilon)$-approximate hopsets. For either object, it is now known that one can use $O(n)$ hop-edges to reduce diameter to $\widetilde{O}(n^{1 / 3})$, improving over the folklore diameter bound of $\widetilde{O}(n^{1 / 2})$. The only setting in which folklore sampling remains unimproved is for exact hopsets. Can these improvements be continued?We settle this question negatively by constructing graphs on which any exact hopset of $O(n)$ edges has diameter $\widetilde{\Omega}(n^{1 / 2})$. This improves on the previous lower bound of $\Omega(n^{1 / 3})$ by Kogan and Parter [FOCS ’22]. Using similar ideas, we also polynomially improve the current lower bounds for shortcut sets, constructing graphs on which any shortcut set of $O(n)$ edges reduces diameter to $\widetilde{\Omega}(n^{1 / 4})$. This improves on the previous lower bound of $\Omega(n^{1 / 6})$ by Huang and Pettie [SIAM J. Disc. Math. ’18]. We also extend our constructions to provide lower bounds against $O(p)$-size exact hopsets and shortcut sets for other values of p; in particular, we show that folklore sampling is near-optimal for exact hopsets in the entire range of parameters $p \in[1, n^{2}]$.

A classic 1993 paper by Althöfer et al. proved a tight reduction from spanners, emulators, and distance oracles to the extremal function $\gamma$ of high-girth graphs. This paper initiated a large body of work in network design, in which problems are attacked by reduction to $\gamma$ or the analogous extremal function for other girth concepts. In this paper, we introduce and study a new girth concept that we call the bridge girth of path systems, and we show that it can be used to significantly expand and improve this web of connections between girth problems and network design. We prove two kinds of results:•We write the maximum possible size of an n-node, p-path system with bridge girth $\gt k$ as $\beta(n, p, k)$, and we write a certain variant for “ordered” path systems as $\beta^{*}(n, p, k)$. We identify several arguments in the literature that implicitly show upper or lower bounds on $\beta, \beta^{*}$, and we provide some polynomial improvements to these bounds. In particular, we construct a tight lower bound for $\beta(n, p, 2)$, and we polynomially improve the upper bounds for $\beta(n, p, 4)$ and $\beta^{*}(n, p, \infty)$.•We show that many state-of-the-art results in network design can be recovered or improved via black-box reductions to $\beta$ or $\beta^{*}$. Examples include bounds for distance/reachability preservers, exact hopsets, shortcut sets, the flow-cut gaps for directed multicut and sparsest cut, an integrality gap for directed Steiner forest.We believe that the concept of bridge girth can lead to a stronger and more organized map of the research area. Towards this, we leave many open problems related to both bridge girth reductions and extremal bounds on the size of path systems with high bridge girth.

A $t$-emulator of a graph $G$ is a graph $H$ that approximates its pairwise shortest path distances up to multiplicative $t$ error. We study fault tolerant $t$-emulators, under the model recently introduced by Bodwin, Dinitz, and Nazari [ITCS 2022] for vertex failures. In this paper we consider the version for edge failures, and show that they exhibit surprisingly different behavior. In particular, our main result is that, for $(2k-1)$-emulators with $k$ odd, we can tolerate a polynomial number of edge faults for free. For example: for any $n$-node input graph, we construct a $5$-emulator ($k=3$) on $O(n^{4/3})$ edges that is robust to $f = O(n^{2/9})$ edge faults. It is well known that $Ω(n^{4/3})$ edges are necessary even if the $5$-emulator does not need to tolerate any faults. Thus we pay no extra cost in the size to gain this fault tolerance. We leave open the precise range of free fault tolerance for odd $k$, and whether a similar phenomenon can be proved for even $k$.

In competitive games, it is common to assign each player a real number rating signifying their skill level. A rating system is a procedure by which player ratings are adjusted upwards each time they win, or downwards each time they lose. Many matchmaking systems give players some control over their opponent’s rating; for example, a player might be able to selectively initiate games against opponents whose ratings are publicly visible, or abort a game without penalty before it begins but after glimpsing their opponent’s rating. It is natural to ask whether one can design a rating system that does not incentivize a rating-maximizing player to act strategically, seeking games against opponents of one rating over another. We show the following: - The full version of this "opponent indifference" property is unfortunately too strong to be feasible. Although it is satisfied by some rating systems, these systems lack certain desirable expressiveness properties, suggesting that they are not suitable to capture most games of interest. - However, there is a natural relaxation, roughly requiring indifference between any two opponents who are both "reasonably evenly matched" with the choosing player. We prove that this relaxed variant of opponent indifference, which we call P opponent indifference, is viable. In fact, a certain strong version of P opponent indifference precisely characterizes the rating system Sonas, which was originally proposed for its empirical predictive accuracy on the outcomes of high-level chess games.

The restoration lemma by Afek et al. [ 3 ] proves that, in an undirected unweighted graph, any replacement shortest path avoiding a failing edge can be expressed as the concatenation of two original shortest paths. However, the lemma is tiebreaking-sensitive : if one selects a particular canonical shortest path for each node pair, it is no longer guaranteed that one can build replacement paths by concatenating two selected shortest paths. They left as an open problem whether a method of shortest path tiebreaking with this desirable property is generally possible. We settle this question affirmatively with the first general construction of restorable tiebreaking schemes . We then show applications to various problems in fault-tolerant network design. These include a faster algorithm for subset replacement paths, more efficient fault-tolerant (exact) distance labeling schemes, fault-tolerant subset distance preservers and + 4 additive spanners with improved sparsity, and fast distributed algorithms that construct these objects. For example, an almost immediate corollary of our restorable tiebreaking scheme is the first nontrivial distributed construction of sparse fault-tolerant distance preservers resilient to three faults.

For an input graph G, an additive spanner is a sparse subgraph H whose shortest paths match those of G up to small additive error. We prove two new lower bounds in the area of additive spanners:•We construct n-node graphs G for which any spanner on $O(n)$ edges must increase a pairwise distance by $+\Omega(n^{1/7})$. This improves on a recent lower bound of $+\Omega(n^{1/10.5})$ by Lu, Wein, Vassilevska Williams, and Xu [SODA 22].•A classic result by Coppersmith and Elkin [SODA 05] proves that for any n-node graph G and set of $p=O(n^{1/2})$ demand pairs, one can exactly preserve all pairwise distances among demand pairs using a spanner on $O(n)$ edges. They also provided a lower bound construction, establishing that that this range $p=O(n^{1/2})$ cannot be improved. We strengthen this lower bound by proving that, for any constant k, this range of p is still unimprovable even if the spanner is allowed $+k$ additive error among the demand pairs. This negatively resolves an open question asked by Coppersmith and Elkin [SODA 05] and again by Cygan, Grandoni, and Kavitha [STACS 13] and Abboud and Bodwin [SODA 16].At a technical level, our lower bounds are obtained by an improvement to the entire obstacle product framework used to compose “inner” and outer” graphs into lower bound instances. In particular, we develop a new strategy for analysis that allows certain non-layered graphs to be used in the product, and we use this freedom to design better inner and outer graphs that lead to our new lower bounds.

A $k$-spanner of a graph $G$ is a sparse subgraph that preserves its shortest path distances up to a multiplicative stretch factor of $k$, and a $k$-emulator is similar but not required to be a subgraph of $G$. A classic theorem by Thorup and Zwick [JACM '05] shows that, despite the extra flexibility available to emulators, the size/stretch tradeoffs for spanners and emulators are equivalent. Our main result is that this equivalence in tradeoffs no longer holds in the commonly-studied setting of graphs with vertex failures. That is: we introduce a natural definition of vertex fault-tolerant emulators, and then we show a three-way tradeoff between size, stretch, and fault-tolerance for these emulators that polynomially surpasses the tradeoff known to be optimal for spanners. We complement our emulator upper bound with a lower bound construction that is essentially tight (within $\log n$ factors of the upper bound) when the stretch is $2k-1$ and $k$ is either a fixed odd integer or $2$. We also show constructions of fault-tolerant emulators with additive error, demonstrating that these also enjoy significantly improved tradeoffs over those available for fault-tolerant additive spanners.

Recent work has established that, for every positive integer k, every n-node graph has a (2k–1)-spanner with O(f1–1/k n1+1/k) edges that is resilient to f edge or vertex faults. For vertex faults, this bound is tight. However, the case of edge faults is not as well understood: the best known lower bound for general k is . Our main result is to nearly close this gap with an improved upper bound, thus separating the cases of edge and vertex faults. For odd k, our new upper bound is , which is tight up to hidden poly(k) factors. For even k, our new upper bound is Ok(f1/2 n1 + 1/k + fn), which leaves a gap of poly(k)f1/(2k). Our proof is an analysis of the fault-tolerant greedy algorithm, which requires exponential time, but we also show that there is a polynomial-time algorithm which creates edge fault tolerant spanners that are larger only by factors of k.

The restoration lemma by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt [Dist. Comp. '02] proves that, in an undirected unweighted graph, any replacement shortest path avoiding a failing edge can be expressed as the concatenation of two original shortest paths. However, the lemma is tiebreaking-sensitive: if one selects a particular canonical shortest path for each node pair, it is no longer guaranteed that one can build replacement paths by concatenating two selected shortest paths. They left as an open problem whether a method of shortest path tiebreaking with this desirable property is generally possible.

Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer k, every n-node graph has a (2k – 1)-spanner on O(f1–1/kn1+1/k) edges resilient to f vertex faults, and there are examples of input graphs on which this bound cannot be improved. However, these proofs work by analyzing the output spanner of a certain exponential-time greedy algorithm. In this work, we give the first algorithm that produces vertex fault tolerant spanners of optimal size and which runs in polynomial time. Specifically, we give a randomized algorithm which takes Õ (f1–1/kn2+1/k + mf2) time. We also derandomize our algorithm to give a deterministic algorithm with similar bounds. This reflects an exponential improvement in runtime over [Bodwin-Patel PODC '19], the only previously known algorithm for constructing optimal vertex fault-tolerant spanners.

Given a graph G = (V,E), a subgraph H is an additive +β spanner if dist_H(u,v) ≤ dist_G(u,v) + β for all u, v ∈ V. A pairwise spanner is a spanner for which the above inequality is only required to hold for specific pairs P ⊆ V × V given on input; when the pairs have the structure P = S × S for some S ⊆ V, it is called a subsetwise spanner. Additive spanners in unweighted graphs have been studied extensively in the literature, but have only recently been generalized to weighted graphs. In this paper, we consider a multi-level version of the subsetwise additive spanner in weighted graphs motivated by multi-level network design and visualization, where the vertices in S possess varying level, priority, or quality of service (QoS) requirements. The goal is to compute a nested sequence of spanners with the minimum total number of edges. We first generalize the +2 subsetwise spanner of [Pettie 2008, Cygan et al., 2013] to the weighted setting. We experimentally measure the performance of this and several existing algorithms by [Ahmed et al., 2020] for weighted additive spanners, both in terms of runtime and sparsity of the output spanner, when applied as a subroutine to multi-level problem. We provide an experimental evaluation on graphs using several different random graph generators and show that these spanner algorithms typically achieve much better guarantees in terms of sparsity and additive error compared with the theoretical maximum. By analyzing our experimental results, we additionally developed a new technique of changing a certain initialization parameter which provides better spanners in practice at the expense of a small increase in running time.

We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers , which are sparse subgraphs that agree with the distances of the original graph on a given set of demand pairs. Prior work on distance preservers has exploited only a simple structural property of shortest paths, called consistency , stating that one can break shortest path ties such that no two paths intersect, split apart, and then intersect again later. We prove that consistency alone is not enough to understand distance preservers, by showing both a lower bound on the power of consistency and a new general upper bound that polynomially surpasses it. Specifically, our new upper bound is that any p demand pairs in an n -node undirected unweighted graph have a distance preserver on O( n 2/3 p 2/3 + np 1/3 edges. We leave a conjecture that the right bound is O ( n 2/3 p 2/3 + n ) or better. The second part of this paper leverages these distance preservers in a new construction of additive spanners , which are subgraphs that preserve all pairwise distances up to an additive error function. We give improved error bounds for spanners with relatively few edges; for example, we prove that all graphs have spanners on O(n) edges with + O ( n 3/7 + ε ) error. Our construction can be viewed as an extension of the popular path-buying framework to clusters of larger radii.

Fault tolerant distance preservers are sparse subgraphs that preserve distances between given pairs of nodes under edge or vertex failures. In this paper, we present the first non-trivial constructions of subset distance preservers, which preserve all distances among a subset of nodes S, that can handle either an edge or a vertex fault. - For an n-vertex undirected weighted graph or weighted DAG G = (V,E) and S ⊆ V, we present a construction of a subset preserver with Õ(|S|n) edges that is resilient to a single fault. In the single pair case (|S| = 2), the bound improves to O(n). We further provide a nearly-matching lower bound of Ω(|S|n) in either setting, and we show that the same lower bound holds conditionally even if attention is restricted to unweighted graphs. - For an n-vertex directed unweighted graph G = (V,E) and r ∈ V, S ⊆ V, we present a construction of a preserver of distances in {r} × S with Õ(n^{4/3} |S|^{5/6}) edges that is resilient to a single fault. In the case |S| = 1 the bound improves to O(n^{4/3}), and for this case we provide another matching conditional lower bound. - For an n-vertex directed weighted graph G = (V, E) and r ∈ V, S ⊆ V, we present a construction of a preserver of distances in {r} × S with Õ(n^{3/2} |S|^{3/4}) edges that is resilient to a single vertex fault. (It was proved in [Greg Bodwin et al., 2017] that the bound improves to O(n^{3/2}) when |S| = 1, and that this is conditionally tight.)

In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing. This work is about the complexity behind these proofs: how hard is it to actually find a winning move in a game, when you know by strategy-stealing that one exists? We prove that this problem is PSPACE-Complete already for Minimum Poset Games and Symmetric Maker-Maker Games, which are simple classes of games that capture two of the main types of strategy-stealing arguments in the current literature.

We give a short and easy upper bound on the worst-case size of fault tolerant spanners, which improves on all prior work and is fully optimal at least in the setting of vertex faults.

This paper develops a structural theory of unique shortest paths in real-weighted graphs. Our main goal is to characterize exactly which sets of node sequences, which we call path systems, can be realized as unique shortest paths in a graph with arbitrary real edge weights. We say that such a path system is strongly metrizable. An easy fact implicit in the literature is that a strongly metrizable path system must be consistent, meaning that no two of its paths may intersect, split apart, and then intersect again. Our main result characterizes strong metrizability via some new forbidden intersection patterns along these lines. In other words, we describe a family of forbidden patterns beyond consistency, and we prove that a path system is strongly metrizable if and only if it is consistent and it avoids all of the patterns in this family. We offer separate (but closely related) characterizations in this way for the settings of directed, undirected, and directed acyclic graphs. Our characterizations are based on a new connection between shortest paths and topology; in particular, our new forbidden patterns are in natural correspondence with two-colored topological 2-manifolds, which we visualize as polyhedra. We believe that this connection may be of independent interest, and we further show that it implies some additional structural corollaries that seem to suggest new and possibly deep-rooted connections between these areas.

In this paper we prove new results about the extremal structure of paths in directed graphs. Say we are given a directed graph G = (V, E) on n nodes, a set of sources S ⊆ V of size |S| = n1/3, and a subset P ⊆ S × V of pairs (s,t) where s ∊ S, of size O(n2/3), such that for all pairs (s,t) ∊ P, there is a path from s to t. Our goal is to remove as many edges from G as possible while maintaining the reachability of all pairs in P. How many edges will we have to keep? Can you always go down to n1+o(1) edges? Or maybe for some nasty graphs G you cannot even go below the simple bound of O(n4/3) edges? Embarrassingly, in a world where graph reachability is ubiquitous in countless scientific fields, the current bounds on the answer to this question are far from tight. In this paper, we make polynomial progress in both the upper and lower bounds for these Reachability Preservers over bounds that were implicit in the literature. We show that in the above scenario, O(n) edges will always be sufficient, and in general one is even guaranteed a subgraph on edges that preserves the reachability of all pairs in P. We complement this with a lower bound graph construction, establishing that the above result fully characterizes the settings in which we are guaranteed a preserver of size O(n). Moreover, we design an efficient algorithm that can always compute a preserver of existentially optimal size. The second contribution of this paper is a new connection between extremal graph sparsification results and classical Steiner Network Design problems. Surprisingly, prior to this work, the osmosis of techniques between these two fields had been superficial. This allows us to improve the state of the art approximation algorithms for the most basic Steiner-type problem in directed graphs from the O(n0.6+ε) of Chlamatac, Dinitz, Kortsarz, and Laekhanukit (SODA’17) to O(n0.577+ε).

A k-spanner of a graph G is a sparse subgraph H whose shortest path distances match those of G up to a multiplicative error k. In this paper we study spanners that are resistant to faults. A subgraph H ⊆ G is an f vertex fault tolerant (VFT) k-spanner if H \ F is a k-spanner of G \ F for any small set F of f vertices that might “fail.” One of the main questions in the area is: what is the minimum size of an f fault tolerant k-spanner that holds for all n node graphs (as a function of f, k and n)? This question was first studied in the context of geometric graphs [Levcopoulos et al. STOC ’98, Czumaj and Zhao SoCG ’03] and has more recently been considered in general undirected graphs [Chechik et al. STOC ’09, Dinitz and Krauthgamer PODC ’11]. In this paper, we settle the question of the optimal size of a VFT spanner, in the setting where the stretch factor k is fixed. Specifically, we prove that every (undirected, possibly weighted) n-node graph G has a (2k – 1)-spanner resilient to f vertex faults with Ok (f1–1/kn1+1/k) edges, and this is fully optimal (unless the famous Erdös Girth Conjecture is false). Our lower bound even generalizes to imply that no data structure capable of approximating distG\F (s, t) similarly can beat the space usage of our spanner in the worst case. To the best of our knowledge, this is the first instance in fault tolerant network design in which introducing fault tolerance to the structure increases the size of the (non-FT) structure by a sublinear factor in f. Another advantage of this result is that our spanners are constructed by a very natural and simple greedy algorithm, which is the obvious extension of the standard greedy algorithm used to build spanners in the non-faulty setting. We also consider the edge fault tolerant (EFT) model, defined analogously with edge failures rather than vertex failures. We show that the same spanner upper bound applies in this setting. Our data structure lower bound extends to the case k = 2 (and hence we close the EFT problem for 3-approximations), but it falls to D(f 1/2-1/(2k) · n1+1/k) for k > 3. We leave it as an open problem to close this gap.

Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say $\tilde{O}(n^{1+\delta})$ bits. There is an inherent tradeoff between the sparsity parameter $\delta$ and the stretch function $f$ of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. It has been known for some time that when $\delta\ge 1/3$ there are schemes with constant additive stretch (distance $d$ is stretched to at most $f(d) = d + O(1)$), and recent results of Abboud and Bodwin show that when $\delta < 1/3$ there are no such schemes. Thus, to get practically efficient graph compression with $\delta \to 0$ we must pay superconstant additive stretch, but exactly how much do we have to pay? In this paper we show that the lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that characterize the asymptotic behavior of the optimal stretch function $f$ for sparsity parameter $\delta \in (0,1/3)$. Specifically, for any integer $k\ge 2$, any compression scheme using $O(n^{1+\frac{1}{2^k-1} - \epsilon})$ bits has a sublinear additive stretch function $f$: $f(d) = d + \Omega(d^{1-\frac{1}{k}})$. This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's $(1+\epsilon,\beta)$-spanners have an essentially optimal tradeoff between $\delta$, $\epsilon$, and $\beta$, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of $(1+\epsilon, O(k/\epsilon)^{k-1})$-spanners with size $O((k/\epsilon)^{h_k} kn^{1+\frac{1}{2^{k+1}-1}})$, where $h_k < 3/4$. This size bound improves on the spanners of Elkin and Peleg (2004), Thorup and Zwick (2006), and Pettie (2009). According to our lower bounds neither the size nor stretch function can be substantially improved. Our lower bound technique exhibits several interesting degrees of freedom in the framework of Abboud and Bodwin. By carefully exploiting these freedoms, we are able to obtain lower bounds for several related combinatorial objects. We get lower bounds on the size of $(\beta,\epsilon)$- hopsets, matching Elkin and Neiman's construction (2016), and lower bounds on shortcutting sets for digraphs that preserve the transitive closure. Our lower bound simplifies Hesse's (2003) refutation of Thorup's conjecture (1992), which stated that adding a linear number of shortcuts suffices to reduce the diameter to polylogarithmic. Finally, we show matching upper and lower bounds for graph compression schemes that work for graph metrics with girth at least $2\gamma+1$. One consequence is that Baswana et al.'s (2010) additive $O(\gamma)$-spanners with size $O(n^{1+\frac{1}{2\gamma+1}})$ cannot be improved in the exponent.

This paper develops a recent line of economic theory seeking to understand public goods economies using methods of topological analysis. Our first main result is a very clean characterization of the economy's core (the standard solution concept in public goods). Specifically, we prove that a point is in the core iff it is Pareto efficient, individually rational, and the set of points it dominates is path connected. While this structural theorem has a few interesting implications in economic theory, the main focus of the second part of this paper is on a particular algorithmic application that demonstrates its utility. Since the 1960s, economists have looked for an efficient computational process that decides whether or not a given point is in the core. All known algorithms so far run in exponential time (except in some artificially restricted settings). By heavily exploiting our new structure, we propose a new algorithm for testing core membership whose computational bottleneck is the solution of O(n) convex optimization problems on the utility function governing the economy. It is fairly natural to assume that convex optimization should be feasible, as it is needed even for very basic economic computational tasks such as testing Pareto efficiency. Nevertheless, even without this assumption, our work implies for the first time that core membership can be efficiently tested on (e.g.) utility functions that admit ``nice'' analytic expressions, or that appropriately defined epsilon-approximate versions of the problem are tractable (by using modern black-box epsilon-approximate convex optimization algorithms).

Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve the distances between given pairs of nodes exactly or with some small additive error, respectively. Since real-world networks are prone to failures, it makes sense to study fault-tolerant versions of the above structures. This turns out to be a surprisingly difficult task. For every small but arbitrary set of edge or vertex failures, the preservers and spanners need to contain replacement paths around the faulted set. Unfortunately, the complexity of the interaction between replacement paths blows up significantly, even from 1 to 2 faults, and the structure of optimal preservers and spanners is poorly understood. In particular, no nontrivial bounds for preservers and additive spanners are known when the number of faults is bigger than 2. Even the answer to the following innocent question is completely unknown: what is the worst-case size of a preserver for a single pair of nodes in the presence of f edge faults? There are no super-linear lower bounds, nor subquadratic upper bounds for f>2. In this paper we make substantial progress on this and other fundamental questions: - We present the first truly sub-quadratic size fault-tolerant single-pair preserver in unweighted (possibly directed) graphs: for any n node graph and any fixed number f of faults, O~(fn^{2-1/2^f}) size suffices. Our result also generalizes to the single-source (all targets) case, and can be used to build new fault-tolerant additive spanners (for all pairs). - The size of the above single-pair preserver grows to O(n^2) for increasing f. We show that this is necessary even in undirected unweighted graphs, and even if you allow for a small additive error: If you aim at size O(n^{2-eps}) for \eps>0, then the additive error has to be \Omega(eps f). This surprisingly matches known upper bounds in the literature. - For weighted graphs, we provide matching upper and lower bounds for the single pair case. Namely, the size of the preserver is Theta(n^2) for f > 1 in both directed and undirected graphs, while for f=1 the size is Theta(n) in undirected graphs. For directed graphs, we have a superlinear upper bound and a matching lower bound. Most of our lower bounds extend to the distance oracle setting, where rather than a subgraph we ask for any compact data structure.

Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say Õ(n1+δ) bits. There is an inherent tradeoff between the sparsity parameter δ and the stretch function f of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. It has been known for some time that when δ > 1/3 there are schemes with constant additive stretch (distance d is stretched to at most f (d) = d + O(1)), and recent results of Abboud and Bodwin show that when δ < 1/3 there are no such schemes. Thus, to get practically efficient graph compression with δ → 0 we must pay super-constant additive stretch, but exactly how much do we have to pay? In this paper we show that the lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that characterize the asymptotic behavior of the optimal stretch function f for sparsity parameter δ ∊ (0,1/3). Specifically, for any integer k ≥ 2, any compression scheme with size has a sublinear additive stretch function f: This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's (1 + ∊, ß)-spanners have an essentially optimal tradeoff between δ, ∊, and β, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of (1 + ∊, O(k/ ∊)k—1)-spanners with size where hk < 3/4. This size bound improves on the spanners of Elkin and Peleg (2004), Thorup and Zwick (2006), and Pet- tie (2009). According to our lower bounds neither the size nor stretch function can be substantially improved. Our lower bound technique exhibits several interesting degrees of freedom in the framework of Abboud and Bodwin. By carefully exploiting these freedoms, we are able to obtain lower bounds for several related combinatorial objects. We get lower bounds on the size of (β, ∊)-hopsets, matching Elkin and Neiman's construction (2016), and lower bounds on shortcut- ting sets for digraphs that preserve the transitive closure. Our lower bound simplifies Hesse's (2003) refutation of Thorup's conjecture (1992), which stated that adding a linear number of shortcuts suffices to reduce the diameter to polylogarithmic. Finally, we show matching upper and lower bounds for graph compression schemes that work for graph metrics with girth at least 2γ + 1. One consequence is that Baswana et al.'s (2010) additive O(7)-spanners with size cannot be improved in the exponent.

The famous shortest path tree lemma states that, for any node s in a graph G = (V, E), there is a subgraph on O(n) edges that preserves all distances between node pairs in the set {s} × V. A very basic question in distance sketching research, with applications to other problems in the field, is to categorize when else graphs admit sparse subgraphs that preserve distances between a set P of p node pairs, where P has some different structure than {s} × V or possibly no guaranteed structure at all. Trivial lower bounds of a path or a clique show that such a subgraph will need Ω(n + p) edges in the worst case. The question is then to determine when these trivial lower bounds are sharp; that is, when do graphs have linear size distance preservers on O(n + p) edges? In this paper, we make the first new progress on this fundamental question in over ten years. We show: 1. All G, P has a distance preserver on O(n) edges whenever p = O(n1/3), even if G is directed and/or weighted. These are the first nontrivial preservers of size O(n) known for directed graphs. 2. All G, P has a distance preserver on O(p) edges whenever and G is undirected and unweighted. Here, RS(n) is the Ruzsa-Szemeredi function from combinatoric graph theory. These are the first nontrivial preservers of size O(p) known in any setting. 3. To preserve distances within a subset of s nodes in a graph, ω(s2) edges are sometimes needed when even if G is undirected and unweighted. For weighted graphs, the range of this lower bound improves to s = o(n2/3). This result reflects a polynomial improvement over lower bounds given by Coppersmith and Elkin (SODA ‘05).

A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality of its approximation, so long as distance error is measured multiplicatively . A central open question in the field is to prove or disprove whether such a tradeoff exists also in the regime of additive error. That is, is it true that for all ε > 0, there is a constant k ε such that every graph has a spanner on O ( n 1+ε ) edges that preserves its pairwise distances up to + k ε ? Previous lower bounds are consistent with a positive resolution to this question, while previous upper bounds exhibit the beginning of a tradeoff curve: All graphs have +2 spanners on O ( n 3/2 ) edges, +4 spanners on Õ ( n 7/5 ) edges, and +6 spanners on O ( n 4/3 ) edges. However, progress has mysteriously halted at the n 4/3 bound, and despite significant effort from the community, the question has remained open for all 0 < ε < 1/3. Our main result is a surprising negative resolution of the open question, even in a highly generalized setting. We show a new information theoretic incompressibility bound: There is no function that compresses graphs into O ( n 4/3 − ε ) bits so distance information can be recovered within + n o(1) error. As a special case of our theorem, we get a tight lower bound on the sparsity of additive spanners: the +6 spanner on O ( n 4/3 ) edges cannot be improved in the exponent, even if any subpolynomial amount of additive error is allowed. Our theorem implies new lower bounds for related objects as well; for example, the 20-year-old +4 emulator on O ( n 4/3 ) edges also cannot be improved in the exponent unless the error allowance is polynomial. Central to our construction is a new type of graph product, which we call the Obstacle Product . Intuitively, it takes two graphs G , H and produces a new graph G ⊗ H whose shortest paths structure looks locally like H but globally like G .

An $α$-spanner of a graph $ G $ is a subgraph $ H $ such that $ H $ preserves all distances of $ G $ within a factor of $ α$. In this paper, we give fully dynamic algorithms for maintaining a spanner $ H $ of a graph $ G $ undergoing edge insertions and deletions with worst-case guarantees on the running time after each update. In particular, our algorithms maintain: (1) a $3$-spanner with $ \tilde O (n^{1+1/2}) $ edges with worst-case update time $ \tilde O (n^{3/4}) $, or (2) a $5$-spanner with $ \tilde O (n^{1+1/3}) $ edges with worst-case update time $ \tilde O (n^{5/9}) $. These size/stretch tradeoffs are best possible (up to logarithmic factors). They can be extended to the weighted setting at very minor cost. Our algorithms are randomized and correct with high probability against an oblivious adversary. We also further extend our techniques to construct a $5$-spanner with suboptimal size/stretch tradeoff, but improved worst-case update time. To the best of our knowledge, these are the first dynamic spanner algorithms with sublinear worst-case update time guarantees. Since it is known how to maintain a spanner using small amortized but large worst-case update time [Baswana et al. SODA'08], obtaining algorithms with strong worst-case bounds, as presented in this paper, seems to be the next natural step for this problem.

A pairwise spanner of a graph G = (V, E) and a “pair set” P ⊆ V × V is a subgraph H that preserves all pairwise distances in P, up to some additive error term +β. When β = 0 the object is called a pairwise distance preserver. A large and growing body of work has considered upper bounds for these objects, but lower bounds have been elusive. The only known lower bound results are (1) Coppersmith and Elkin (SODA'05) against preservers, and (2) considerably weaker bounds by Woodruff (FOCS'06) against spanners. Our main result is an amplification theorem: we prove that lower bounds against pairwise distance preservers imply lower bounds against pairwise spanners. In other words, to prove lower bounds against any constant error spanners, it is enough to consider only subgraphs that are not allowed any error at all! We apply this theorem to obtain drastically improved lower bounds. Some of these include: Linear size pairwise spanners with up to +(2k – 1) error cannot span |P| = ω(n(1+k)/(3+k)) pairs. This is a large improvement over Woodruff's |P| = ω(n2–2/k) (|P| is now linear, rather than quadratic, as k gets large). |E(H)| = Ω(n1+1/k) edges are required for a +(2k – 1) spanner of |P| = Ω(n1+1/k) pairs – this is another large improvement over Woodruff's |P| = Ω(n2). The first tight bounds for pairwise spanners: for +2 error and P = ⊝(n3/2) we show that ⊝(n3/2) edges are necessary and sufficient (this also reflects a new upper bound: we construct +2 pairwise spanners on O(n|P|1/3) edges, removing a log factor from a prior algorithm). We also show analogous improved lower bounds against subset spanners (where P = S × S for some node subset S), and the first lower bounds against D threshold spanners (where P is the set of node pairs at distance at least D).

We make improvements to the upper bounds on several popular types of distance preserving graph sketches. The first part of our paper concerns pairwise distance preservers, which are sparse subgraphs that exactly preserve the pairwise distances for a set of given pairs of vertices. Our main result here is that all unweighted, undirected n-node graphs G and all pair sets P have distance preservers on |H| = O(n2/3|P|2/3 + n|P|1/3) edges. This improves the known bounds whenever |P| = ω(n3/4). We then develop a new graph clustering technique, based on distance preservers, and we apply this technique to show new upper bounds for additive (standard) spanners, in which all pairwise distances must be preserved up to an additive error function, and for subset spanners, in which only distances within a given node subset must be preserved up to an error function. For both of these objects, we obtain the new best tradeoff between spanner sparsity and error allowance in the regime where the error is polynomial in the graph size. We leave open a conjecture that O(n2/3|P|2/3 + n) pairwise distance preservers are possible for undirected unweighted graphs. Resolving this conjecture in the affirmative would improve and simplify our upper bounds for all the graph sketches mentioned above.

Graph reconstruction algorithms seek to learn a hidden graph by repeatedly querying a black-box oracle for information about the graph structure. Perhaps the most well studied and applied version of the problem uses a distance oracle, which can report the shortest path distance between any pair of nodes. We introduce and study the betweenness oracle, where bet(a, m, z) is true iff m lies on a shortest path between a and z. This oracle is strictly weaker than a distance oracle, in the sense that a betweenness query can be simulated by a constant number of distance queries, but not vice versa. Despite this, we are able to develop betweenness reconstruction algorithms that match the current state of the art for distance reconstruction, and even improve it for certain types of graphs. We obtain the following algorithms: (1) Reconstruction of general graphs in O(n^2) queries, (2) Reconstruction of degree-bounded graphs in ~O(n^{3/2}) queries, (3) Reconstruction of geodetic degree-bounded graphs in ~O(n) queries In addition to being a fundamental graph theoretic problem with some natural applications, our new results shed light on some avenues for progress in the distance reconstruction problem.

A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality of its approximation, so long as distance error is measured multiplicatively. A central open question in the field is to prove or disprove whether such a tradeoff exists also in the regime of additive error. That is, is it true that for all ε>0, there is a constant kε such that every graph has a spanner on O(n1+ε) edges that preserves its pairwise distances up to +kε? Previous lower bounds are consistent with a positive resolution to this question, while previous upper bounds exhibit the beginning of a tradeoff curve: all graphs have +2 spanners on O(n3/2) edges, +4 spanners on Õ(n7/5) edges, and +6 spanners on O(n4/3) edges. However, progress has mysteriously halted at the n4/3 bound, and despite significant effort from the community, the question has remained open for all 0 < ε < 1/3.

We obtain new upper bounds on the additive distortion for graph emulators and spanners on relatively few edges. We introduce a new subroutine called "strip creation," and we combine this subroutine with several other ideas to obtain the following results: