<p>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.</p>

<p>In my <a href="http://www.stanford.edu/~rrwill/cnf-sat-feasible.pdf">SODA'10 paper with Mihai Patrascu</a> 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 &gt; 0$, then there is a $2^{N(1-\varepsilon/2)}poly(M)$ time algorithm for CNF-SAT on $N$ variables and $M$ clauses. </p>

<p>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. </p>

CC BY-SA 3.0
2013-08-31T13:19:38.943Z
2013-08-31T13:19:38.943Z
Ryan Williams
<p>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$.</p>

<p>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 &lt; 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$.</p>

CC BY-SA 3.0
2013-08-30T21:10:18.357Z
More generally, the case $m = n^{O(1)}$ is NP-hard, and the case $m = n^{o(1)}$ is not NP-hard assuming ETH, since there is a $\mathrm{poly}(n,2^m)$ algorithm.
Yuval Filmus
CC BY-SA 3.0
2013-08-30T19:14:56.033Z
2013-08-30T19:14:56.033Z
Yuval Filmus
<p>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, </p>

<p>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 </p>

<p>\begin{align*}
         \text{SET-COVER'}=\{&lt;\mathcal{U}, \mathcal{F}, k&gt;:
         &amp;\text{ there exists at most $k$ subsets }\\
         &amp;\text{ $S_{i_1}, \cdots, S_{i_k}\in \mathcal{F}$ that cover $\mathcal{U}$}
         \}.
\end{align*}</p>

<p>What if $m=O(\sqrt{n})$? </p>

<p>Any result based on well known conjectures (e.g., Unique Games, ETH) is good. </p>

<p>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?</p>

<p>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).</p>

CC BY-SA 3.0
2013-08-30T19:05:56.753Z
There exists a better algorithm to decide the problem in time $m^{O(m)}$ (more precisely the Bell number for $m$): for each partition of the elements into subsets, test whether there exists an input set covering each subset. So for $m=O(\log n/\log\log n)$ the problem can be solved in polynomial time. This doesn't quite answer your question about $m=O(\log n)$, though.
David Eppstein
<np-hardness><set-cover><exp-time-algorithms>
Hardness of a subcase of Set Cover
user1297
# Hardness of a subcase of Set Cover

(Asked by: username_0 on 2013-08-30)

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).

**Tags:** np-hardness, set-cover, exp-time-algorithms
> **Comments:**
> **username_1**: There exists a better algorithm to decide the problem in time $m^{O(m)}$ (more precisely the Bell number for $m$): for each partition of the elements into subsets, test whether there exists an input set covering each subset. So for $m=O(\log n/\log\log n)$ the problem can be solved in polynomial time. This doesn't quite answer your question about $m=O(\log n)$, though.  

---

## 2 answers

### Answer by username_2 on 2013-08-31. Score: 12

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](http://www.stanford.edu/~rrwill/cnf-sat-feasible.pdf) 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 by username_3 on 2013-08-30. Score: 11

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$.

> **Comments:**
> **username_3**: More generally, the case $m = n^{O(1)}$ is NP-hard, and the case $m = n^{o(1)}$ is not NP-hard assuming ETH, since there is a $\mathrm{poly}(n,2^m)$ algorithm.  

---

