TY - JOUR

T1 - Steiner transitive-closure spanners of low-dimensional posets

AU - Berman, Piotr

AU - Bhattacharyya, Arnab

AU - Grigorescu, Elena

AU - Raskhodnikova, Sofya

AU - Woodruff, David P.

AU - Yaroslavtsev, Grigory

N1 - Funding Information:
* A preliminary version of this paper appeared in ICALP 2011 [7]. † Supported by NSF CCF-1065125, 0728645, 0832797, 0830673 and 0528414. Research done while at Massachusetts Institute of Technology, USA. ‡ Supported in part by NSF award CCR-0829672 and NSF award 1019343 to the Computing Research Association for the Computing Innovation Fellowship Program. § S. R. and G. Y. are supported by NSF / CCF CAREER award 0845701. G.Y. is also supported by University Graduate Fellowship and College of Engineering Fellowship.

PY - 2014/6

Y1 - 2014/6

N2 - 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. In some applications, the shortcut paths added to the graph in order to obtain small diameter can use Steiner vertices, that is, vertices not in the original graph G. The resulting spanner is called a Steiner transitive-closure spanner (Steiner TC-spanner). Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TC-spanners of directed acyclic graphs or, equivalently, partially ordered sets. In these applications, the goal is to find a sparsest Steiner k-TC-spanner of a poset G for a given k and G. The focus of this paper is the relationship between the dimension of a poset and the size of its sparsest Steiner TC-spanner. The dimension of a poset G is the smallest d such that G can be embedded into a d-dimensional directed hypergrid via an order-preserving embedding. We present a nearly tight lower bound on the size of Steiner 2-TC-spanners of d- dimensional directed hypergrids. It implies better lower bounds on the complexity of local reconstructors of monotone functions and functions with small Lipschitz constant. The lower bound is derived from an explicit dual solution to a linear programming relaxation of the Steiner 2-TC-spanner problem. We also give an efficient construction of Steiner 2-TC-spanners, of size matching the lower bound, for all low-dimensional posets. Finally, we present a lower bound on the size of Steiner k-TC-spanners of d-dimensional posets. It shows that the best-known construction, due to De Santis et al., cannot be improved significantly.

AB - 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. In some applications, the shortcut paths added to the graph in order to obtain small diameter can use Steiner vertices, that is, vertices not in the original graph G. The resulting spanner is called a Steiner transitive-closure spanner (Steiner TC-spanner). Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TC-spanners of directed acyclic graphs or, equivalently, partially ordered sets. In these applications, the goal is to find a sparsest Steiner k-TC-spanner of a poset G for a given k and G. The focus of this paper is the relationship between the dimension of a poset and the size of its sparsest Steiner TC-spanner. The dimension of a poset G is the smallest d such that G can be embedded into a d-dimensional directed hypergrid via an order-preserving embedding. We present a nearly tight lower bound on the size of Steiner 2-TC-spanners of d- dimensional directed hypergrids. It implies better lower bounds on the complexity of local reconstructors of monotone functions and functions with small Lipschitz constant. The lower bound is derived from an explicit dual solution to a linear programming relaxation of the Steiner 2-TC-spanner problem. We also give an efficient construction of Steiner 2-TC-spanners, of size matching the lower bound, for all low-dimensional posets. Finally, we present a lower bound on the size of Steiner k-TC-spanners of d-dimensional posets. It shows that the best-known construction, due to De Santis et al., cannot be improved significantly.

UR - http://www.scopus.com/inward/record.url?scp=84903122026&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84903122026&partnerID=8YFLogxK

U2 - 10.1007/s00493-014-2833-9

DO - 10.1007/s00493-014-2833-9

M3 - Article

AN - SCOPUS:84903122026

SN - 0209-9683

VL - 34

SP - 255

EP - 277

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -