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

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] \gets \infty$ for all $\emptyset \neq V \subseteq U$, and $T[\emptyset] = 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]$.
• 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)$. Jul 29, 2018 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. Jul 29, 2018 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)$. Jul 29, 2018 at 12:02
• Thank you very much, but I still wonder if there exist a $O(2^n)$ algorithm even when $m=2^n$.
– wst
Jul 29, 2018 at 14:46
• Unfortunately I can't help you with that. Jul 29, 2018 at 15:14