Theory Seminar, Wednesday Nov 27: Idan Shabat (BGU) - On the Size Overhead of Pairwise Spanners
Arnold Filtser
Title: On the Size Overhead of Pairwise Spanners
Abstract: Given a pair of vertices in an undirected weighted graph,
we consider their distance as the weight of the lightest path between them. For
sparsifying the input graph, a common goal is to produce a spanner –
a subgraph in which the distances are not much larger than in the original
graph.
Unfortunately, a simple argument shows that many graphs cannot have a small spanner, if we wish to obtain a stretch (multiplicative error) close to 1. One possible solution is to allow also a small additive error. These near-additive spanners, however, make sense only for unweighted graphs.
A different solution is to ensure a small stretch only for some of the vertex-pairs in the graph, which were defined in advance. We denote the given set of pairs by P, and we call the resulting spanner a pairwise spanner. A pairwise spanner can be constructed even for weighted graph.
In our paper, we note that the size of known pairwise spanners is asymptotic to |P| times some factor, which we call the size overhead. Remarkably, the size overhead of the state-of-the-art pairwise spanner is the same quantity as the state-of-the-art additive error of near-additive spanners. It is also the same as some other parameters that appear in different structures like hopsets and emulators. We prove a lower bound on the size of pairwise spanners, which essentially implies that this parameter must appear there, and we also show upper and lower bounds on this size overhead for larger stretch (not necessarily close to 1).
A joint work with Ofer Neiman.