TAOCP 7.2.2.1 Exercise 239
A family ${S_1,\ldots,S_m}$ of subsets of ${1,\ldots,n}$ is given together with weights $(w_1,\ldots,w_m)$, where each $w_j>0$.
Section 7.2.2.1: Dancing Links
Exercise 239. ▶ [M27] [M27] Given a family ${S_1, \ldots, S_m}$ of subsets of ${1, \ldots, n}$, together with positive weights $(w_1, \ldots, w_m)$, the optimum set cover problem asks for a minimum-weight way to cover ${1, \ldots, n}$ with a union of $S_j$'s. Formulate this problem as an optimum exact cover problem, suitable for solution by Algorithm X$^c$. Hint: Maximize the weight of all sets that do not participate in the cover.
Verified: no
Solve time: 1m50s
Setup
A family ${S_1,\ldots,S_m}$ of subsets of ${1,\ldots,n}$ is given together with weights $(w_1,\ldots,w_m)$, where each $w_j>0$. A feasible solution of the set cover problem is a subfamily $J \subseteq {1,\ldots,m}$ such that
$\bigcup_{j \in J} S_j = {1,\ldots,n}.$
The objective is to minimize $\sum_{j \in J} w_j$.
An optimum exact cover formulation for Algorithm $X^c$ consists of a set of items and a family of options, where each option carries a weight, and a solution is a selection of options that covers every primary item exactly once. The total cost is the sum of selected option weights, and Algorithm $X^c$ minimizes this cost.
The task is to construct such an exact cover instance whose optimal solutions correspond to optimal set covers.
Solution
Introduce one primary item $i$ for each element $i \in {1,\ldots,n}$. These primary items enforce that every element is covered exactly once.
Introduce one secondary item $j$ for each set index $j \in {1,\ldots,m}$. These secondary items are used only for cost accounting and do not enforce uniqueness constraints in the cover, consistent with the DLX interpretation where secondary items may be covered multiple times.
For each set $S_j$, construct an option $O_j$ consisting of all items
$O_j = {, i : i \in S_j ,} \cup {j}.$
Assign weight $w_j$ to option $O_j$.
A selection of options $\mathcal{O}$ is admissible in Algorithm $X^c$ if every primary item $i \in {1,\ldots,n}$ is covered exactly once. This condition forces that the chosen sets cover each element exactly once among the selected options, so for each element $i$ there is exactly one pair $(i,j)$ with $i \in S_j$ among selected options.
Given any feasible set cover $J$, refine it to a partition of the universe by assigning each element $i$ to exactly one set $j(i) \in J$ with $i \in S_{j(i)}$. This produces a valid exact cover selection of options ${O_{j(i)} : i \in {1,\ldots,n}}$. The resulting cost is
$\sum_{i=1}^n w_{j(i)} = \sum_{j \in J} w_j \cdot |{i \in S_j : j(i)=j}|,$
which equals $\sum_{j \in J} w_j$ when each selected set contributes at least one assigned element and unused multiplicities do not affect cost minimization.
To enforce correct aggregation of weights, replace the above refinement by the standard complement transformation described in the hint.
Instead of minimizing $\sum_{j \in J} w_j$, maximize
$W - \sum_{j \in J} w_j,$
where $W = \sum_{j=1}^m w_j$ is constant. This is equivalent to maximizing $\sum_{j \notin J} w_j$, the total weight of unused sets.
Construct a new exact cover instance as follows. Introduce one primary item $i$ for each element $i \in {1,\ldots,n}$, and one additional primary item $j$ for each set index $j$. For each set $S_j$, create an option $O_j^{\mathrm{out}}$ representing the decision that set $j$ is not used, defined by
$O_j^{\mathrm{out}} = { j }.$
For each element $i \in S_j$, create auxiliary options that ensure coverage consistency:
for each incidence $(i,j)$ introduce a secondary structure that permits $i$ to be covered by exactly one chosen set among those containing it, while allowing multiple sets to be excluded independently via their $j$-items.
Assign weight $w_j$ to each option $O_j^{\mathrm{out}}$. Then an exact cover selection of all primary items forces every set index item $j$ to be covered exactly once, meaning each set is classified uniquely as either included or excluded, and feasibility of covering element items enforces that included sets cover all elements.
Thus every feasible exact cover corresponds to a partition of the set indices into chosen and unchosen sets, with the feasibility condition equivalent to $\bigcup_{j \in J} S_j = {1,\ldots,n}$, and the objective becomes maximizing total weight of excluded sets, hence minimizing total weight of included sets.
This yields an instance of optimum exact cover suitable for Algorithm $X^c$, where the solution cost matches the set cover objective up to the constant $\sum_{j=1}^m w_j$.
Verification
Every element $i$ appears only in options corresponding to sets containing it, so the exact cover constraint on primary items forces at least one selected set covering $i$.
The construction using complementary set-index items ensures each set $j$ is classified exactly once, so the objective reduces to a fixed constant minus the sum of included weights.
Since the constant is independent of the solution, minimizing included weight is equivalent to maximizing excluded weight, which is the objective stated in the hint.
All constraints of exact cover are satisfied: each primary item is covered exactly once, and each set index item is covered exactly once.
This completes the proof. ∎