How hard is the Set Cover problem if the number of elements is boundedby some function (e.g, $\log n$) where $n$ is the size of the problem instance. Formally, Let $\mathcal{U}=\{e_1, \cdots, e_m\}$ and $\mathcal{F} = \{S_1, \cdots, S_n\}$where $S_i \subseteq \mathcal{U}$ and $m = O(\log n)$. How hard is it to decide the following problem \begin{align*}         \text{SET-COVER'}=\{<\mathcal{U}, \mathcal{F}, k>:         &\text{ there exists at most $k$ subsets }\\         &\text{ $S_{i_1}, \cdots, S_{i_k}\in \mathcal{F}$ that cover $\mathcal{U}$}         \}.\end{align*}What if $m=O(\sqrt{n})$? Any result based on well known conjectures (e.g., Unique Games, ETH) is good. Edit 1: A motivation for this problem is finding out when the problem gets hard as $m$ increases. Clearly, the problem is in P if $m=O(1)$ and NP-hard if $m=O(n)$. What is the threshold for the NP-hardness of the problem?Edit 2 : There exists a trivial algorithm to decide it in time $O(n^{m})$ (which enumerates all subsets of size $m$ of $\mathcal{F}$). Therefore, the problem is not NP-hard if $m=O(\log{n})$ since ETH implies that there is no algorithm in time $O(2^{n^{o(1)}})$ for any NP-hard problem (where $n$ is the size of the NP-hard problem).
Hardness of a subcase of Set Cover
np hardness;set cover;exp time algorithms