3.45 P.M.
Transitive-Closure Spanners
Arnab Bhattacharya
MIT, U.S.A.
27-01-11

---

Abstract

Given a directed graph G = (V,E) and a positive integer k, define a k-transitive-closure spanner (k-TC-spanner) of G to be a directed graph H = (V, E') that (1) has the same transitive closure as G, and (2) has diameter at most k. These spanners (and some variants) have been implicitly studied in sublinear-time algorithms, access control, and data structures, and properties of these spanners have been rediscovered multiple times over the span of 20 years. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners.

In this talk, we will survey the applications of TC-spanners. We will also describe combinatorial bounds on the size of the sparsest TC-spanners for natural graph families, as well as algorithms and inapproximability results for the problem of computing the sparsest TC-spanner of a given directed graph.

Based on several works co-authored with: Piotr Berman, Elena Grigorescu, Madhav Jha, Kyomin Jung, Konstantin Makarychev, Sofya Raskhodnikova, David Woodruff and Grigory Yaroslavtsev.