Optimal Information Rate of Secret Sharing Schemes on Trees
László Csirmaz, Gábor Tardos · IEEE Transactions on Information Theory · 2012
The information rate for an access structure is the reciprocal of the load of the optimal secret sharing scheme for this structure. We determine this value for all trees: it is (2-1/c)-1, wherecis the size of the largest core of the tree. A subset of the vertices of a tree is a core if it induces a connected subgraph and for each vertex in the subset one finds a neighbor outside the subset. Our result follows from a lower and an upper bound on the information rate that applies for any graph and happen to coincide for trees because of a correspondence between the size of the largest core and a quantity related to a fractional cover of the tree with stars.