Source author record

Greg Bodwin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics math.CO

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Partially Optimal Edge Fault-Tolerant Spanners

Recent work has established that, for every positive integer $k$ , every $n$ -node graph has a $(2k-1)$ -spanner on $O(f^{1-1/k} n^{1+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 $Ω(f^{\frac12 - \frac{1}{2k}} n^{1+1/k} +fn)$ . 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 $O_k(f^{\frac12 - \frac{1}{2k}} n^{1+1/k} + fn)$ , which is tight up to hidden $poly(k)$ factors. For even $k$ , our new upper bound is $O_k(f^{1/2} n^{1+1/k} +fn)$ , which leaves a gap of $poly(k) f^{1/(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$ .

preprint2020arXiv

Graph Spanners: A Tutorial Review

This tutorial review provides a guiding reference to researchers who want to have an overview of the large body of literature about graph spanners. It reviews the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners.

preprint2020arXiv

New Results on Linear Size Distance Preservers

Given $p$ node pairs in an $n$ -node graph, a distance preserver is a sparse subgraph that agrees with the original graph on all of the given pairwise distances. We prove the following bounds on the number of edges needed for a distance preserver: - Any $p$ node pairs in a directed weighted graph have a distance preserver on $O(n + n^{2/3} p)$ edges. - Any $p = Ω\left(\frac{n^2}{rs(n)}\right)$ node pairs in an undirected unweighted graph have a distance preserver on $O(p)$ edges, where $rs(n)$ is the Ruzsa-Szemerédi function from combinatorial graph theory. - As a lower bound, there are examples where one needs $ω(σ^2)$ edges to preserve all pairwise distances within a subset of $σ= o(n^{2/3})$ nodes in an undirected weighted graph. If we additionally require that the graph is unweighted, then the range of this lower bound falls slightly to $σ\le n^{2/3 - o(1)}$ .

preprint2020arXiv

The 4/3 Additive Spanner Exponent is Tight

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 \emph{additive} error. That is, is it true that for all $\varepsilon>0$ , there is a constant $k_{\varepsilon}$ such that every graph has a spanner on $O(n^{1+\varepsilon})$ edges that preserves its pairwise distances up to $+k_{\varepsilon}$ ? 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 $\tilde{O}(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 < \varepsilon < 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 - \varepsilon})$ bits so that 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 twenty-year-old $+4$ emulator on $O(n^{4/3})$ edges also cannot be improved in the exponent unless the error allowance is polynomial.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Greg Bodwin

Research overview

Is this your work?

4 publications

Partially Optimal Edge Fault-Tolerant Spanners

Graph Spanners: A Tutorial Review

New Results on Linear Size Distance Preservers

The 4/3 Additive Spanner Exponent is Tight

See the researcher in context

Building this map preview