most recent 30 from http://mathoverflow.net 2013-06-20T01:14:23Z http://mathoverflow.net/feeds/question/94045 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94045/covering-set-problem David Harris 2012-04-14T17:23:21Z 2012-04-14T18:14:39Z

<p>All the references I can find to Covering Set appear to be algorithmic. Is there are any reference for the simple existential question ---</p> <p>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$. </p> <p>Given fixed values for $k, n, t$ what is the largest $Y$ which might be necessary to do this?</p> <p>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)$. </p> <p>If I am not concerned with an algorithm for finding $Y$, only guaranteeing that it exists, is there any asymptotically better result possible?</p>

http://mathoverflow.net/questions/94045/covering-set-problem/94048#94048 JeffE 2012-04-14T18:14:39Z 2012-04-14T18:14:39Z

<p>You've described the classical <a href="http://www.shannarasite.org/kb/kbse42.html" rel="nofollow">hitting set</a> problem; it's NP-hard.</p> <p>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.</p>