63 The Set Cover Problem

Problem Definition

• Given a set $U\in \{u_1,u_2,\cdots ,u_N\}$ of $N$ elements
• A set $S=\{S_1,S_2,\cdots ,S_M\}$ of non-empty subsets of $U$ such that $|S|=M$
• Question is to find a collection $S^{\prime }$ from $S$ of minimum size such that the union of sets in $S^{\prime }$ covers all elements of $U$
• Assumption: Union of all sets in $S$ covers all elements of $U$

Brute force algorithm: Takes $O(2^M\cdot M\cdot N)$ time

• Tries all possible $2^M$ subsets of $S$
• Given one such subset $S^{\prime }$ we can check in $O(M\cdot N)$ time if union of all sets in $S^{\prime }$ covers all elements of $U$
  • Each of the $\le M$ sets in $S^{\prime }$ can have at most $N$ elements each
• Can we do better, say $O(2^N\cdot N\cdot M)$ time ?
  • Note that $1\le M\le 2^N$

Setting up the recurrence for dynamic programming

• For each non-empty subset $X\subseteq U$ and each $1\le j\le M$ let $\mathrm{OPT}[X,j]$ be the size of minimum cardinality subset of $\{S_1,S_2,\cdots ,S_j\}$ that covers all elements from $X$.
  • Find a recurrence for $\mathrm{OPT}[X,j]$
  • What happens if $\{S_1,S_2,\cdots ,S_j\}$ does not cover $X$
• Base case is when $j=1$