Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

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 studied implicitly in access control, property testing, and data structures, and properties of these spanners have been rediscovered over the span of 20 years. We bring these areas under the unifying framework of TC-spanners. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners.

We study the approximability of the size of the sparsest k-TC-spanner for a given digraph. Our technical contributions fall into three categories: algorithms for general digraphs, inapproximability results, and structural bounds for a specific graph family which imply an efficient algorithm with a good approximation ratio for that family.

Algorithms. We present two efficient deterministic algorithms that find k-TC-spanners of near optimal size. The first algorithm gives an Õ(n^1-1/k)-approximation for k > 2. Our method, based on a combination of convex programming and sampling, yields the first sublinear approximation ratios for (1) Directed k-Spanner, a well-studied generalization of k-TC-Spanner, and (2) its variants Client/Server Directed k-Spanner, and the k-Diameter Spanning Subgraph. This resolves the main open question of Elkin and Peleg (IPCO, 2001). The second algorithm, specific to the k-TC-spanner problem, gives an Õ(n/k²)-approximation. It shows that for k = Ω(√n), our problem has a provably better approximation ratio than Directed k-Spanner and its variants. This algorithm also resolves an open question of Hesse (SODA, 2003).

Inapproximability. Our main technical contribution is a pair of strong inapproximability results. We resolve the approximability of 2-TC-spanners, showing that it is θ(log n) unless P = NP. For constant k ≥ 3, we prove that the size of the sparsest k-TC-spanner is hard to approximate within 2^log1-ε n, for any ε > 0, unless NP ⊆ DTIME (n^{polylog n}). Our hardness result helps explain the difficulty in designing general efficient solutions for the applications above, and it cannot be improved without resolving a long-standing open question in complexity theory. It uses an involved application of generalized butterfly and broom graphs, as well as noise-resilient transformations of hard problems, which may be of independent interest.

Structural bounds. Finally, we study the size of the sparsest TC-spanner for H-minor-free digraphs, which include planar, bounded genus, and bounded tree-width graphs, explicitly investigated in applications above. We show that every H-minor-free digraph has an efficiently con-structible k-TC-spanner of size Õ(n). This implies an Õ(1)-approximation algorithm for this family. Furthermore, using our insight that 2-TC-spanners yield property testers, we obtain a monotonicity tester with O(log² n/ε) queries for any poset whose transitive reduction is an H-minor free digraph. This improves and generalizes the previous θ(√n log n/ε)-query tester of Fischer et al (STOC, 2002).

REFERENCES

• 1: Ittai Abraham , Cyril Gavoille, Object location using path separators, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146411]
• 2: W. Ackermann. Zum Hilbertshen aufbau der reelen zahlen. Math. Ann., 99:118--133, 1928.
• 3: A. V. Aho, M. R. Garey, and J. D. Ullman. The transitive reduction of a directed graph. SIAM J. Comput., 1(2):131--137, 1972.
• 4: Nir Ailon , Bernard Chazelle, Information theory in property testing and monotonicity testing in higher dimension, Information and Computation, v.204 n.11, p.1704-1717, November 2006 [doi>10.1016/j.ic.2006.06.001]
• 5: N. Alon and B. Schieber. Optimal preprocessing for answering on-line product queries. Technical Report 71/87, Tel-Aviv University, 1987.
• 6: Ingo Althöfer , Gautam Das , David Dobkin , Deborah Joseph , José Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry, v.9 n.1, p.81-100, 1993 [doi>10.1007/BF02189308]
• 7: Mikhail J. Atallah , Marina Blanton , Keith B. Frikken, Key management for non-tree access hierarchies, Proceedings of the eleventh ACM symposium on Access control models and technologies, June 07-09, 2006, Lake Tahoe, California, USA [doi>10.1145/1133058.1133062]
• 8: Mikhail J. Atallah , Keith B. Frikken , Marina Blanton, Dynamic and efficient key management for access hierarchies, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102147]
• 9: Surender Baswana , Sandeep Sen, Approximate distance oracles for unweighted graphs in expected O(n²) time, ACM Transactions on Algorithms (TALG), v.2 n.4, p.557-577, October 2006 [doi>10.1145/1198513.1198518]
• 10: A. Bhattacharyya, E. Grigorescu, K. Jung, S. Raskhodnikova, and D. P. Woodruff. Transitive-closure spanners. http://arxiv.org/abs/0808.1787, 2008.
• 11: B. Chazelle. Computing on a free tree via complexity-preserving mappings. Algorithmica, 2:337--361, 1987.
• 12: Chandra Chekuri , Guy Even , Anupam Gupta , Danny Segev, Set connectivity problems in undirected graphs and the directed Steiner network problem, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.532-541, January 20-22, 2008, San Francisco, California
• 13: Edith Cohen, Fast Algorithms for Constructing t-Spanners and Paths with Stretch t, SIAM Journal on Computing, v.28 n.1, p.210-236, Feb. 1999 [doi>10.1137/S0097539794261295]
• 14: Edith Cohen, Polylog-time and near-linear work approximation scheme for undirected shortest paths, Journal of the ACM (JACM), v.47 n.1, p.132-166, Jan. 2000 [doi>10.1145/331605.331610]
• 15: Lenore J. Cowen, Compact routing with minimum stretch, Journal of Algorithms, v.38 n.1, p.170-183, Jan. 2001 [doi>10.1006/jagm.2000.1134]
• 16: Lenore J. Cowen , Christopher G. Wagner, Compact roundtrip routing in directed networks, Journal of Algorithms, v.50 n.1, p.79-95, January 2004 [doi>10.1016/j.jalgor.2003.08.001]
• 17: Yevgeniy Dodis , Oded Goldreich , Eric Lehman , Sofya Raskhodnikova , Dana Ron , Alex Samorodnitsky, Improved Testing Algorithms for Monotonicity, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.97-108, August 08-11, 1999
• 18: Yevgeniy Dodis , Sanjeev Khanna, Design networks with bounded pairwise distance, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.750-759, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301447]
• 19: Michael Elkin, Computing almost shortest paths, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.53-62, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383983]
• 20: Michael Elkin , David Peleg, Strong Inapproximability of the Basic k-Spanner Problem, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.636-647, July 09-15, 2000
• 21: M. Elkin and D. Peleg. The client-server 2-spanner problem with applications to network design. In SIROCCO, pages 117--132, 2001.
• 22: Michael Elkin , David Peleg, Approximating k-spanner problems for k > 2, Theoretical Computer Science, v.337 n.1-3, p.249-277, 9 June 2005 [doi>10.1016/j.tcs.2004.11.022]
• 23: Michael Elkin , David Peleg, The Hardness of Approximating Spanner Problems, Theory of Computing Systems, v.41 n.4, p.691-729, December 2007 [doi>10.1007/s00224-006-1266-2]
• 24: Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Journal of Computer and System Sciences, v.60 n.3, p.717-751, June 2000 [doi>10.1006/jcss.1999.1692]
• 25: Eldar Fischer, On the strength of comparisons in property testing, Information and Computation, v.189 n.1, p.107-116, 25 February 2004 [doi>10.1016/j.ic.2003.09.003]
• 26: Eldar Fischer , Eric Lehman , Ilan Newman , Sofya Raskhodnikova , Ronitt Rubinfeld , Alex Samorodnitsky, Monotonicity testing over general poset domains, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509977]
• 27: O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samorodnitsky. Testing monotonicity. Combinatorica, 20(3):301--337, 2000.
• 28: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 29: S. Halevy and E. Kushilevitz. Testing monotonicity over graph products. In ICALP, pages 721--732, 2004.
• 30: William Hesse, Directed graphs requiring large numbers of shortcuts, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 31: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 32: G. Kortsarz. On the hardness of approximating spanners. Algorithmica, 30(3):432--450, 2001.
• 33: Guy Kortsarz , David Peleg, Generating sparse 2-spanners, Journal of Algorithms, v.17 n.2, p.222-236, Sept. 1994 [doi>10.1006/jagm.1994.1032]
• 34: R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177--189, 1979.
• 35: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 36: D. Peleg and A. A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99--116, 1989.
• 37: David Peleg , Jeffrey D. Ullman, An optimal synchronizer for the hypercube, SIAM Journal on Computing, v.18 n.4, p.740-747, Aug. 1989 [doi>10.1137/0218050]
• 38: David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
• 39: Liam Roditty , Mikkel Thorup , Uri Zwick, Roundtrip spanners and roundtrip routing in directed graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.844-851, January 06-08, 2002, San Francisco, California
• 40: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
• 41: A. D. Santis, A. L. Ferrara, and B. Masucci. Efficient provably-secure hierarchical key assignment schemes. In MFCS, pages 371--382, 2007.
• 42: Mikkel Thorup, On Shortcutting Digraphs, Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science, p.205-211, June 19-20, 1992
• 43: M. Thorup. Shortcutting planar digraphs. Combinatorics, Probability & Computing, 4:287--315, 1995.
• 44: Mikkel Thorup, Parallel shortcutting of rooted trees, Journal of Algorithms, v.23 n.1, p.139-159, April 1997 [doi>10.1006/jagm.1996.0829]
• 45: Mikkel Thorup, Compact oracles for reachability and approximate distances in planar digraphs, Journal of the ACM (JACM), v.51 n.6, p.993-1024, November 2004 [doi>10.1145/1039488.1039493]
• 46: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]
• 47: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Journal of the ACM (JACM), v.52 n.1, p.1-24, January 2005 [doi>10.1145/1044731.1044732]
• 48: David P. Woodruff, Lower Bounds for Additive Spanners, Emulators, and More, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.389-398, October 21-24, 2006 [doi>10.1109/FOCS.2006.45]
• 49: Andrew C. Yao, Space-time tradeoff for answering range queries (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.128-136, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802185]
• 50: U. Zwick. Exact and approximate distances in graphs --- A survey. Lecture Notes in Computer Science, 2161:33+, 2001.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
      G.1.6 Optimization
          Subjects: Convex programming

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms