Recent work has pinned down the existentially optimal size bounds for vertex faulttolerant spanners: for any positive integer k, every nnode graph has a (2k – 1)spanner on O(f^{1–1/k} n^{1+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 exponentialtime 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 Õ(f^{1–1/k} n^{2+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 [BodwinPatel PODC '19], the only previously known algorithm for constructing optimal vertex faulttolerant spanners.
Local Computation Algorithms for Spanners
A graph spanner is a fundamental graph structure that faithfully preserves the pairwise distances in the input graph up to a small multiplicative stretch. The common objective in the computation of spanners is to achieve the bestknown existential sizestretch tradeoff efficiently.
Classical models and algorithmic analysis of graph spanners essentially assume that the algorithm can read the input graph, construct the desired spanner, and write the answer to the output tape. However, when considering massive graphs containing millions or even billions of nodes not only the input graph, but also the output spanner might be too large for a single processor to store.
To tackle this challenge, we initiate the study of local computation algorithms (LCAs) for graph spanners in general graphs, where the algorithm should locally decide whether a given edge (u,v)∈E belongs to the output spanner. Such LCAs give the user the `illusion' that a specific sparse spanner for the graph is maintained, without ever fully computing it. We present the following results:
For general nvertex graphs and r∈{2,3}, there exists an LCA for (2r−1)spanners with O˜(n1+1/r) edges and sublinear probe complexity of O˜(n1−1/2r). These size/stretch tradeoffs are best possible (up to polylogarithmic factors).
For every k≥1 and nvertex graph with maximum more »
 Publication Date:
 NSFPAR ID:
 10108397
 Journal Name:
 Innovations in Theoretical Computer Science (ITCS)
 Sponsoring Org:
 National Science Foundation
More Like this


Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing largescale graphs. By now, we have quite fast algorithmsusually sublogarithmictime and often poly(łogłog n)time, or even fasterfor a number of fundamental graph problems in the massively parallel computation (MPC) model. This model is a widelyadopted theoretical abstraction of MapReduce style settings, where a number of machines communicate in an alltoall manner to process largescale data. Contributing to this line of work on MPC graph algorithms, we present poly(łog k) ε poly(łogłog n) round MPC algorithms for computing O(k^1+o(1) )spanners in the strongly sublinear regime of local memory. To the best of our knowledge, these are the first sublogarithmictime MPC algorithms for spanner construction. As primary applications of our spanners, we get two important implications, as follows: For the MPC setting, we get an O(łog^2łog n)round algorithm for O(łog^1+o(1) n) approximation of all pairs shortest paths (APSP) in the nearlinear regime of local memory. To the best of our knowledge, this is the first sublogarithmictime MPC algorithm for distance approximations. Our result above also extends to the Congested Clique model of distributed computing, with the same round complexity and approximation guarantee. This gives the first sublogarithmic algorithmmore »

A spanner of a graph G is a subgraph H that approximately preserves shortest path distances in G. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measured multiplicatively. In this work, we investigate whether one can similarly extend constructions of spanners with purely additive error to weighted graphs. These extensions are not immediate, due to a key lemma about the size of shortest path neighborhoods that fails for weighted graphs. Despite this, we recover a suitable amortized version, which lets us prove direct extensions of classic +2 and +4 unweighted spanners (both allpairs and pairwise) to +2W and +4W weighted spanners, where W is the maximum edge weight. Specifically, we show that a weighted graph G contains allpairs (pairwise) +2W and +4W weighted spanners of size O(n3/2) and O(n7/5) (O(np1/3) and O(np2/7)) respectively. For a technical reason, the +6 unweighted spanner becomes a +8W weighted spanner; closing this error gap is an interesting remaining open problem. That is, we show that G contains allpairs (pairwise) +8W weighted spanners of size O(n4/3) (O(np1/4)).

In the model of local computation algorithms (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recently developed LCAs on graph problems achieve time and space complexities with very low dependence on n, the number of vertices. Nonetheless, these complexities are generally at least exponential in d, the upper bound on the degree of the input graph. Instead, we consider the case where parameter d can be moderately dependent on n, and aim for complexities with subexponential dependence on d, while maintaining polylogarithmic dependence on n. We present: a randomized LCA for computing maximal independent sets whose time and space complexities are quasipolynomial in d and polylogarithmic in n; for constant ε>0, a randomized LCA that provides a (1−ε)approximation to maximum matching with high probability, whose time and space complexities are polynomial in d and polylogarithmic in n.

We study several fundamental problems in the kmachine model, a messagepassing model for largescale distributed computations where k ≥ 2 machines jointly perform computations on a large input of size N, (typically, N ≫ k). The input is initially partitioned (randomly or in a balanced fashion) among the k machines, a common implementation in many realworld systems. Communication is pointtopoint, and the goal is to minimize the number of communication rounds of the computation. Our main result is a general technique for designing efficient deterministic distributed algorithms in the kmachine model using PRAM algorithms. Our technique works by efficiently simulating PRAM algorithms in the kmachine model in a deterministic way. This simulation allows us to arrive at new algorithms in the kmachine model for some problems for which no efficient kmachine algorithms are known before and also improve on existing results in the kmachine model for some problems. While our simulation allows us to obtain kmachine algorithms for any problem with a known PRAM algorithm, we mainly focus on graph problems. For an input graph on n vertices and m edges, we obtain Õ(m/k 2 ) round 4 algorithms for various graph problems such as rconnectivity for r = 1,more »