Hardness of a subcase of Set Cover

Question

How hard is the Set Cover problem if the number of elements is bounded by 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).

Answer 1

The case of $m = c \log n$ is in $n^{O(c)}$ time as noted by Yuval, but also note for $k = O(1)$ you can solve the problem in $O(n^k \cdot m)$ time (polynomial time) by exhaustive search. Assuming the Strong Exponential Time Hypothesis (that CNF-SAT on formulas with $N$ variables and $O(N)$ clauses requires at least $2^{N-o(N)}$ time), these two time bounds are the "limit" of what we can expect in polynomial time, in the following sense.

In my SODA'10 paper with Mihai Patrascu we study the essentially isomorphic problem of finding a dominating set of size $k$ in an arbitrary $n$-node graph, showing that if $k$-dominating set can be solved in $n^{k-\varepsilon}$ time for some $k \geq 2$ and $\varepsilon > 0$, then there is a $2^{N(1-\varepsilon/2)}poly(M)$ time algorithm for CNF-SAT on $N$ variables and $M$ clauses.

Noting the relationship between neighborhoods of vertices in a dominating set instance and sets in a set cover instance, and inspecting the reduction, you will find that this reduction also shows solving $k$-Set Cover with $n$ sets over a universe of size $m$ in $n^{k-\varepsilon}\cdot f(m)$ time implies a CNF-SAT algorithm for CNF formulas with $M$ clauses and $N$ variables running in $2^{N(1-\varepsilon/2)}\cdot f(M)$ time. For the purposes of refuting the Strong ETH, it suffices to solve CNF-SAT in the case where $M = O(N)$. Hence an algorithm for your problem running in $n^{k-\varepsilon}\cdot 2^{m/\alpha(m)}$ time for some unbounded function $\alpha(m)$ would yield a surprising new SAT algorithm.

Answer 2

When $m = O(\log n)$, you can use dynamic programming to find the optimum in polynomial time. The table contains Boolean-valued cells $T_{\ell,X}$ for each $\ell \in \{0,\ldots,k\}$ and $X \subseteq \mathcal{U}$, indicating whether there are $\ell$ sets which cover the elements in $X$.

When $m = O(\sqrt{n})$, say $m \leq C\sqrt{n}$, the problem remains NP-hard. Given an instance of SET-COVER, add $m$ new elements $x_1,\ldots,x_m$ and $(2C^{-1}m)^2$ new sets, consisting of non-empty subsets of the new elements, including $\{x_1,\ldots,x_m\}$ (when $m$ is large enough, $(2C^{-1}m)^2 < 2^m$). Also increase $k$ by one. The new $m,n$ are $m' = 2m$ and $n' = n + (2C^{-1}m)^2 \geq (C^{-1}m')^2$.