# Covering set problem

All the references I can find to Covering Set appear to be algorithmic. Is there are any reference for the simple existential question ---

Suppose we have $k$ sets $X_1,…,X_k$ which are subsets of a ground set $X$ of size $n$. We know that $|X_i| \geq t$ for all $X_i$. We would like to find the smallest set $Y$ such that $Y \cap X_i \neq \emptyset$ for all $i$.

Given fixed values for $k, n, t$ what is the largest $Y$ which might be necessary to do this?

The greedy algorithm for constructing $Y$ is to add the element of $X$ to maximize the number of $X_i$ covered in each stage. Apparently this requires $|Y| = O(\frac{n}{t} \log k)$.

If I am not concerned with an algorithm for finding $Y$, only guaranteeing that it exists, is there any asymptotically better result possible?

-
(As JeffE said, this is a hitting set, not a covering set.) It seems that choosing a random hitting set large enough so that the expected number of sets missed is less than 1 also provides an upper bound of the form $O(n\log k/t)$, though surely the constant is worse. – Brendan McKay Apr 15 '12 at 13:44

Moreover, given an oracle that determines whether there is a hitting set of size $k$ in polynomial time, it is easy to construct an algorithm that actually computes a hitting set of size $k$ in polynomial time plus a polynomial number of calls to the existence oracle. (Details are left as a homework exercise.) So the existence problem and the construction problem are polynomial-time equivalent.
@Gerhard: My understanding is that David wants a good upper bound on the minimum hitting set as a function only of $k,t,n$, not as a function of the actual sets presented. David, is that right? – Brendan McKay Apr 15 '12 at 13:39