Consider the following instance of Set Cover problem:
- Universe U={a,b,c,d}
- Family F={S1={a,c},S2={a,d},S3={b,d},S4={b,c}}
We use dynamic programming to find the minimum number of sets from F required to cover U. Recall that for every X⊆U and every 0≤j≤∣F∣, our algorithm computes and stores Π(X,j), i.e., minimum number of sets from Fj={S1,…,Sj} required to cover X.
Consider the following DP table:
| {a,b,c,d} | ∞ | ∞ | ∞ | 2 | 2 |
|---|
| {b,c,d} | ∞ | ∞ | ∞ | 2 | 2 |
| {a,c,d} | ∞ | ∞ | 2 | 2 | 2 |
| {a,b,d} | ∞ | ∞ | ∞ | 2 | 2 |
| {a,b,c} | ∞ | ∞ | ∞ | 2 | 2 |
| {c,d} | ∞ | ∞ | 2 | 2 | 2 |
| {b,d} | ∞ | ∞ | ∞ | 1 | 1 |
| {b,c} | ∞ | ∞ | ∞ | 2 | 1 |
| {a,d} | ∞ | ∞ | 1 | 1 | 1 |
| {a,c} | ∞ | 1 | 1 | 1 | 1 |
| {a,b} | ∞ | ∞ | ∞ | 2 | 2 |
| {d} | ∞ | ∞ | 1 | 1 | 1 |
| {c} | ∞ | 1 | 1 | 1 | 1 |
| {b} | ∞ | ∞ | ∞ | 1 | 1 |
| {a} | ∞ | 1 | 1 | 1 | 1 |
| Φ | 0 | 0 | 0 | 0 | 0 |
| X / j | 0 | 1 | 2 | 3 | 4 |
Based on the above data, answer the given subquestions.
