2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ (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. $\endgroup$
    – Brendan McKay
    Commented Apr 15, 2012 at 13:44

1 Answer 1

Reset to default
3
$\begingroup$

You've described the classical hitting set problem; it's NP-hard.

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ This shows that the size is hard to determine, not that it is hard to approximate. The question asked is whether O((n log k)/t) is the right order of magnitude, or is there something provably smaller. If you have approximation results or evem an example (well, family of examples) where Y has that order of magnitude, that would answer the question. Gerhard "Ask Me About System Design" Paseaman, 2012.04.14 $\endgroup$
    – Gerhard Paseman
    Commented Apr 14, 2012 at 18:47
  • $\begingroup$ As I said, I am not interested in algorithmics, only the existence of covering set. $\endgroup$
    – David Harris
    Commented Apr 14, 2012 at 19:27
  • $\begingroup$ David Harris, I respectfully disagree with your comment. The existence of such a set is trivial; you are interested in good, or at least better than obvious, upper bounds on the size of such a set. A good part of algorithmics is in determining such bounds, and I think you will benefit most from approximation results, which JeffE might be able to provide. Even if you don't want to see how the result is made, I think you will be interested in the taste, which to me means you care at least about the output of the algorithmics process. Gerhard "But I've Been Wrong Before" Paseman, 2012.04.14 $\endgroup$
    – Gerhard Paseman
    Commented Apr 14, 2012 at 20:45
  • 1
    $\begingroup$ @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? $\endgroup$
    – Brendan McKay
    Commented Apr 15, 2012 at 13:39
  • $\begingroup$ @Gerhard: I'm having trouble extracting your interpretation of the question from the written text. I misinterpreted the last sentence as "I am not concerned with an algorithm for finding Y, only for determining whether it exists...". $\endgroup$
    – JeffE
    Commented Apr 15, 2012 at 18:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .