TAOCP 7.2.2.1 Exercise 169

Section 7.2.2.1: Dancing Links

Exercise 169. ▶ [22] [22] Let $G$ be a graph with $n$ vertices. Formulate the problem of finding all of its $t$-element independent sets as an MCC problem with $1 + n$ items and $n$ options.

Verified: no
Solve time: 3m10s

Solution

Let the vertices of $G$ be $v_1, v_2, \dots, v_n$. Introduce $1+n$ items in the MCC instance: one special primary item $c$ and, for each vertex $v_i$, an item also denoted $v_i$. The item $c$ will control the size of the independent set.

For each vertex $v_i$, define one option

$$ O_i = {c} \cup {v_i} \cup {v_j : v_j \text{ is adjacent to } v_i}. $$

This yields exactly $n$ options.

In the MCC interpretation, each item $v_i$ has upper bound $1$, and the item $c$ has upper bound $t$. Each option $O_i$ contributes one occurrence of $c$ and one occurrence of each item listed in $O_i$.

Suppose a collection of options corresponds to a set $S \subseteq {v_1,\dots,v_n}$. The MCC constraints require that no item exceeds its upper bound. The item $c$ is covered exactly $|S|$ times because each selected option contributes exactly one occurrence of $c$, hence $|S| \le t$ and, in a valid solution, equality $|S|=t$ must hold.

For a vertex item $v_i$, its total coverage equals the number of selected options $O_j$ such that $v_i \in O_j$. By construction this occurs precisely when $j=i$ or when $v_j$ is adjacent to $v_i$. Thus, if $S$ contains two adjacent vertices $v_i$ and $v_j$, then both $O_i$ and $O_j$ contain both $v_i$ and $v_j$, so each of these two items is covered at least twice, violating the upper bound $1$. Hence no two adjacent vertices can both lie in $S$, so $S$ is an independent set.

Conversely, let $S$ be an independent set of size $t$. For each $v_i \in S$, select option $O_i$. Each vertex item $v_i \in S$ appears in $O_i$ and in no other selected option, since no neighbor of $v_i$ lies in $S$. Each vertex item $v_i \notin S$ appears in no selected option. Thus every vertex item is covered at most once, and every selected option respects the upper bound $1$ on vertex items. The item $c$ is covered exactly $t$ times, matching its upper bound.

Therefore the selected options form a feasible MCC solution if and only if the corresponding vertex set is a $t$-element independent set.

This completes the reduction of the problem to an MCC instance with $1+n$ items and $n$ options. ∎