TRANSITIVE-CLOSURE SPANNERS

Abstract

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, EH) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were implicitly studied in the context of circuit complexity, data structures, property testing, and access control, and properties of these spanners have been rediscovered 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. We initiate the study of approximability of the size of the sparsest k-TC-spanner of a given directed graph. We completely resolve the approximability of 2-TC-spanners, showing that it is Theta(log n) unless P = NP. For k > 2, we present a polynomial time algorithm that finds a k-TC-spanner with size within O((n log n)(1-1/k)) of the optimum. Our techniques also yield algorithms with the first nontrivial approximation ratio for well-studied problems on directed spanners when k > 3: Directed k-SPANNER, CLIENT/SERVER DIRECTED k-SPANNER, and k-DIAMETER SPANNING SUBGRAPH. For constant k >= 3, we show that the size of the sparsest k-TC-spanner is hard to approximate within a factor of 2log(1-epsilon) n for any epsilon is an element of (0, 1) unless NP subset of DTIME(n(polylog n)). Finally, we study the size of the sparsest k-TC-spanners for H-minor-free graph families. Combining our constructions with our insight that 2-TC-spanners can be used for designing property testers, we obtain a monotonicity tester with O(log(2) n/epsilon) queries for any poset whose transitive reduction, when viewed as an undirected graph, is free of a fixed minor. Previously, the best upper bound on the query complexity for such graphs was O(root n/epsilon).