What is the expected size of the smallest hitting set?

Question

Suppose we pick $n$ subsets of size $j$ of an $N$-element set $S$ uniformly at random. A hitting set is a subset of $S$ that intersects all our subsets. I am interested in the smallest size of an hitting set.

What is its expected value?

For example for $n=2$, we get that the smallest cardinality is one, if the chosen sets are not disjoint and two if they are. The probability that two chosen subsets are disjoint is $\prod_{i=N-j}^{N-2j-1}\frac{i}{N}$. Now I am looking at a formula/good approximation of the general case.

In general the problem to find a minimal hitting set is NP-hard, so it might be quite difficult to say something by hand. But sometimes finding expected values turns out to be easier than solving specific cases, so I still have not lost hope yet that an explicit formula might be possible.

Answer 1

I don't know how to give a formula for the mean. However the following gives an approach that is often useful asymptotically. Its success depends on the relation between $n$, $N$, $j$, which you did not specify.

Let $A_k$ denote the $k$th random subset. Fix a parameter $l$. Define the random variable $Z_l=\sum_{B\subset S: |B|\leq l} \prod_{k=1}^n 1_{B\cap A_k\neq \emptyset}$. Note that $Z_l\geq 1$ iff there is a hitting set of size $\leq l$. That is your minimal hitting set is precisely the minimal $l$ such that $Z_l\geq 1$.

The advantage of $Z_l$ is that its mean and second moment are easily computed. For example, if I did not make a mistake, $$ EZ_l=\sum_{m=1}^l\binom{N}{m}(1- \frac{(N-m-j)!(N-j)!}{(N-m)! N!})^n$$ and a similar expression can be written for $EZ_l^2$ (it is uglier but certainly amenable to asymptotic analysis) — just decompose according to the number of sets $B_1,B_2$ of size $m_1,m_2\leq l$ and overlap $m_3$.

Now, your minimal set is certainly larger with high probability (when parameters go to infinity in some way, as you hinted in your discussion on NP hardness) than any $l=l(N,n,j)$ for which $EZ_l\to 0$. Similarly, it is certainly smaller than any $l$ for which $EZ_l\to \infty$ AND $EZ_l^2/(EZ_l)^2\leq C$ with good probability (close to 1 if $C\sim 1$) because $$P(Z_l\geq 1)\geq (EZ_l)^2/EZ_l^2$$ which follows from Cauchy–Schwarz.

Often, this gives excellent estimates, and I believe will do so here as well, depending on the asymptotic you choose for your parameters.

Answer 2

A greedy algorithm lets us pick an element that it's at least $\lceil j n/N \rceil $ of the sets, leaving us with at most $n- \lceil j n/N \rceil $ subsets of size $j$ of an $N-1$-element set. We can iterate this process. The upper bound for the set $S$ we get from this is around $ \log n / (j/N)$ in some ranges.

I expect the upper bound from the greedy algorithm to be close to sharp in some regimes, which removes the need for the second moment estimate mentioned by ofer zeitouni.

---

This problem has a few different regimes. When $nj^2/N$ is small the average subset overlaps less than one other subset, and we can just choose the hitting set to be all elements lying in two or more subsets plus one element from each subset which does not overlap any other subset. The size of the minimal hitting set will be $n - n^2j^2/(2N)$ plus lower-order terms.

When $nj /N \log N$ is large, every element is in approximately the same number of subsets and the greedy bound should be close to sharp, with the first moment lower bound of ofer zeitouni probably sufficient to prove this.

In between these the situation is more complicated.