期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 . Transitive-closure spanners were introduced in \cite{tc-spanners-soda} as a common abstraction for applications in access control, property testing and data structures. In this work we study the number of edges in the sparsest 2-TC-spanners for the directed hypercube 0 1 d and hypergrid 1 2 m d with the usual partial order, , defined by: x 1 x d y 1 y d if and only if x i y i for all i 1 d . We show that the number of edges in the sparsest 2-TC-spanner of the hypercube is 2 cd + ( log d ) , where c 1 1620 We also present upper and lower bounds on the size of the sparsest 2-TC-spanner of the directed hypergrid. Our first pair of upper and lower bounds for the hypergrid is in terms of an expression with binomial coefficients. The bounds differ by a factor of O ( d 2 m ) and, in particular, give tight (up to a pol y ( d ) factor) bounds for constant m . We also give a second set of bounds, which show that the number of edges in the sparsest 2-TC-spanner of the hypergrid is at most m d log d m and at least ( max m d ( log d m ) ((2 d log log m ) d − 1 ) ( m − 1 ) d 2 ( c + − 1) d ) , where c 1 1620 , as above, and 0"> 0 satisfies 1 + H b ( ) c . The two sets of bounds are, in general, incomparable. Our results rule out a class of approaches to monotonicity testing of functions of the form f : 0 1 d R and, more generally, f : 1 2 m d R , where R is an arbitrary range. \cite{tc-spanners-soda} showed that sparse 2-TC-spanners imply fast monotonicity testers, and used this connection to improve existing monotonicity testers for planar and other H -minor-free graphs. It left open the question, which was again raised at the 2008 Dagstuhl seminar on Sublinear Algorithms, of whether the 2-TC-spanner approach can improve monotonicity testers on the hypercube and hypergrid. We show that a fundamentally new approach is required.
E ) and an integer k 
