Transitive-Closure Spanners, with Applications to Access Control, Data Structures, and Property Testing

Arnab Bhattacharyya (MIT)

We define the notion of a transitive-closure spanner of a directed graph. Given a directed graph G = (V,E) and an integer k>=1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, E_H) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were implicitly studied in access control, data structures, and property testing, and properties of these spanners have been rediscovered over the span of 20 years. We bring these areas under the unifying framework of obtaining sparse TC-spanners.

The most technically difficult part of our paper is our strong inapproximability results. We resolve the approximability of the important case of 2-TC-spanners, showing that it is Theta(log n) unless P = NP. For constant k>=3, we then prove that the size of the sparsest k-TC-spanner is hard to approximate within 2^{log^{1-eps} n}, for any epsilon>0, unless NP subseteq DTIME (n^{polylog n}). Our hardness result uses an involved application of generalized butterfly and broom graphs, as well as noise-resilient transformations of well-known hard problems. Our result cannot be improved without resolving a long-standing open question in complexity theory.

For upper bounds, for k>2, we present an efficient algorithm that finds a k-TC-spanner with size within tilde{O}(n^{1-1/k}) of the optimum. Our algorithm uses a combination of convex programming and sampling, and our method yields the first sublinear approximation ratios for Directed k-Spanner, a well-studied generalization of k-TC-Spanner. We give a different tilde{O}(n/k^2)-approximation algorithm specific to the k-TC-spanner problem, showing that for k =Omega(sqrt{n}) there is a gap between our problem and the problems above. This algorithm also answers a question of Hesse. (SODA, 2003)

Finally, we study the size of the sparsest k-TC-spanners for specific graph families: H-minor free graphs. This leads us to obtaining a monotonicity tester with O(log^2 n /epsilon) queries for any poset whose transitive reduction is an H-minor free digraph. This class includes planar, bounded genus, and bounded tree-width graphs, for which the best monotonicity testers to date, due to Fischer et. al. (STOC, 2002), required Theta(sqrt{n} log n/epsilon) queries.

This is joint work with Elena Grigorescu and Kyomin Jung and Sofya Raskhodnikova and David P. Woodruff.

Host: Ronitt Rubinfeld

(The Algorithms and Complexity Seminar series talks are usually held Thursdays 4:00-5:15pm in 32-G575.)