###
L. Csirmaz and G. Tardos:

##
Secret sharing on trees: problem solved

We determine the worst case information rate for all secret sharing
schemes based on trees. It is the inverse of 2-1/*c*, where *c*
is the size
of the maximal core in the tree. A *core* is a connected subset of the
vertices so that every vertex in the core has a neighbor outside the core.
The upper bound comes from an application of the entropy method,
while the lower bound is achieved by a construction using Stinson's
decomposition theorem.

It is shown that 2-1/*c* is also the *fractional cover number*
of the tree where the edges of the tree are covered by stars, and the
vertex cover should be minimized. We also give
an *O*(*n*^{2}) algorithm which finds an optimal
cover on any tree, and thus a perfect secret sharing scheme with optimal
rate.

**Keywords.** Secret sharing scheme; information rate; graph;
fractional packing and cover; entropy method.

Full paper(PDF, 150k)