# How to find the optimum solution of Weighted set cover in O(2^n)

A weighted set cover problem is:

Given a universe $U=\{1,2,...,n\}$ and a collection of subsets of $U$, $\mathcal S=\{S_1,S_2,...,S_m\}$, and a cost function $c:\mathcal S\to Q^+$ , find a minimum cost subcollection of $\mathcal S$ that covers all elements of $U$.

The question is how to design a deterministic algorithm to solve weighted set cover in $O(2^n)$ (just find the optimum solution)?

If I simply use exhaust searching to look through all possible cover (which is actually equals to $2^m$) and find the one with minimum weight, it will cost $O(2^m)$ but not $O(2^n)$.

Use dynamic programming. For every $i \in [m]$ and every $V \subseteq U$, compute the minimal weight of sets among $S_1,\ldots,S_i$ needed to cover $V$.

Here is pseudocode, which uses $w_i$ for the weight of $S_i$:

1. Set $T[V][0] \gets \infty$ for all $\emptyset \neq V \subseteq U$, and $T[\emptyset][0] = 0$.
2. For $i = 1,\ldots,m$:
• Set $T[V][i] \gets T[V][i-1]$ for all $V \subseteq U$.
• Set $T[V \cup S_i][i] \gets \min(T[V \cup S_i][i], T[V][i-1] + w_i)$ for all $V \subseteq U$.
3. Return $T[U][m]$.
• Sorry, could you please explain this algorithm more clearly? I can hardly understand how it function. – wst Jul 29 '18 at 10:17
• I suggest reviewing dynamic programming. – Yuval Filmus Jul 29 '18 at 10:49
• Correct me if I'm wrong, but this looks like $O(m 2^n)$ complexity, which can be upper-bounded by $O(2^{2n})$ if you make sure the sets are unique. I don't see how to get this to $O(2^n)$. – Matej Lieskovsky Jul 29 '18 at 11:21
• When people say $O(2^n)$, they usually mean $\tilde{O}(2^n)$. The number of sets $m$ is usually much smaller than $2^n$ — say, polynomial in $n$. In that case we get a $\tilde{O}(2^n)$ algorithm. – Yuval Filmus Jul 29 '18 at 11:48
• Looking at the literature on exponential time algorithms, it seems that the commonly used notation is $O^*(2^n)$, which hides polynomial factors in both $n$ and $m$. The algorithm I describe clearly runs in $O^*(2^n)$. – Yuval Filmus Jul 29 '18 at 12:02