{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:38:07Z","timestamp":1787341087029,"version":"build-2736575974"},"reference-count":76,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Given a directed graph $G = (V,E)$ and an integer $k \\geq 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 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 $\\textsf{P} = \\textsf{NP}$. For $k&gt;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&gt;3$: Directed $k$-Spanner, Client\/Server Directed $k$-Spanner, and $k$-Diameter Spanning Subgraph. For constant $k \\geq 3$, we show that the size of the sparsest $k$-TC-spanner is hard to approximate within a factor of $2^{\\log^{1-\\eps} n}$ for any $\\eps \\in (0,1)$ unless $\\NP \\subseteq \\text{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 \/\\eps)$ 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(\\sqrt{n\/\\eps})$.<\/jats:p>","DOI":"10.1137\/110826655","type":"journal-article","created":{"date-parts":[[2012,11,13]],"date-time":"2012-11-13T10:39:07Z","timestamp":1352803147000},"page":"1380-1425","source":"Crossref","is-referenced-by-count":21,"title":["Transitive-Closure Spanners"],"prefix":"10.1137","volume":"41","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elena","family":"Grigorescu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kyomin","family":"Jung","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,11,13]]},"reference":[{"key":"atypb1","first-page":"188","author":"Abraham I.","year":"2006","journal-title":"New York"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/0201008"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.06.001"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"atypb5","unstructured":"N. Alon and B. Schieber,\n                      Optimal Preprocessing for Answering On-line Product Queries\n                      , Technical Report 71\/87, Tel Aviv University, Tel Aviv, Israel, 1987."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"atypb7","first-page":"489","author":"Arya S.","year":"1995","journal-title":"New York"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/1455526.1455531"},{"key":"atypb9","first-page":"11","author":"Atallah M. J.","year":"2006","journal-title":"New York"},{"key":"atypb10","first-page":"190","author":"Atallah M. J.","year":"2005","journal-title":"New York"},{"key":"atypb11","first-page":"272","author":"Awerbuch B.","year":"1985","journal-title":"New York"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198518"},{"key":"atypb13","first-page":"760","author":"Berman P.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb14","first-page":"1","author":"Berman P.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"P. Berman and M. Karpinski,\n                      On Some Tighter Inapproximability Results\n                      , Technical Report 85193-CS, DIMACS, Piscataway, NJ, 1998.","DOI":"10.1007\/3-540-48523-6_17"},{"key":"atypb16","first-page":"424","author":"Berman P.","year":"2010","journal-title":"Germany"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/100808186"},{"key":"atypb18","first-page":"932","author":"Bhattacharyya A.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb19","first-page":"111","volume":"1","author":"Bodlaender H. L.","year":"1994","journal-title":"Nordic J. Comput."},{"key":"atypb20","first-page":"109","author":"Chandra A. K.","year":"1983","journal-title":"Heidelberg"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90015-7"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840366"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921664"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331610"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1134"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.08.001"},{"key":"atypb28","first-page":"323","author":"Dinitz M.","year":"2011","journal-title":"New York"},{"key":"atypb29","first-page":"97","author":"Dodis Y.","year":"1999","journal-title":"Berlin"},{"key":"atypb30","first-page":"750","author":"Dodis Y.","year":"1999","journal-title":"New York"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327908"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"atypb33","first-page":"636","author":"Elkin M.","year":"2000","journal-title":"Berlin"},{"key":"atypb34","first-page":"117","author":"Elkin M.","year":"2001","journal-title":"Canada"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.11.022"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1266-2"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1692"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"atypb40","first-page":"922","author":"Feldman M.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.003"},{"key":"atypb42","first-page":"474","author":"Fischer E.","year":"2002","journal-title":"New York"},{"key":"atypb43","unstructured":"C. Gavoille,\n                      Personal communication\n                      , 2007."},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"atypb46","first-page":"721","author":"Halevy S.","year":"2004","journal-title":"Berlin"},{"key":"atypb47","first-page":"665","author":"Hesse W.","year":"2003","journal-title":"Philadelphia"},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"D. Hochbaum, ed.\n                      Approximation Algorithms for NP-hard Problems\n                      , PWS Publishing Company, Boston, 1997.","DOI":"10.1145\/261342.571216"},{"key":"atypb49","first-page":"433","author":"Jha M.","year":"2011","journal-title":"Proceedings of the FOCS"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0021-y"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1032"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268753"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"atypb54","first-page":"286","author":"Lund C.","year":"1993","journal-title":"New York"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1007\/BF01364272"},{"key":"atypb56","doi-asserted-by":"crossref","unstructured":"G. Narasimhan and M. H. M. Smid,\n                      Geometric Spanner Networks\n                      , Cambridge University Press, Cambridge, UK, 2007.","DOI":"10.1017\/CBO9780511546884"},{"key":"atypb57","doi-asserted-by":"crossref","unstructured":"D. Peleg,\n                      Distributed Computing: A Locality-sensitive Approach\n                      , SIAM, Philadelphia, 2000.","DOI":"10.1137\/1.9780898719772"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"atypb61","first-page":"167","author":"Raskhodnikova S.","year":"2010","journal-title":"Heidelberg"},{"key":"atypb62","first-page":"475","author":"Raz R.","year":"1997","journal-title":"New York"},{"key":"atypb63","first-page":"844","author":"Roditty L.","year":"2002","journal-title":"Philadelphia"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"atypb65","first-page":"371","author":"Santis A. De","year":"2007","journal-title":"Berlin"},{"key":"atypb66","first-page":"820","author":"Solomon S.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb67","first-page":"48","author":"Solomon S.","year":"2010","journal-title":"Berlin"},{"key":"atypb68","first-page":"205","author":"Thorup M.","year":"1993","journal-title":"Berlin"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001668"},{"key":"atypb70","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0829"},{"key":"atypb71","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"atypb72","first-page":"1","author":"Thorup M.","year":"2001","journal-title":"New York"},{"key":"atypb73","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"atypb74","first-page":"389","author":"Woodruff D. P.","year":"2006","journal-title":"NJ"},{"key":"atypb75","first-page":"128","author":"A.","year":"1982","journal-title":"New York"},{"key":"atypb76","first-page":"33","author":"Zwick U.","year":"2001","journal-title":"Berlin"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110826655","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:05:11Z","timestamp":1787339111000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110826655"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":76,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/110826655"],"URL":"https:\/\/doi.org\/10.1137\/110826655","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}