TAOCP 7.1.3 Exercise 133

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 133. ▶ [20] [20] Given a graph G, how can the algorithm of exercise 132 be used to find (a) all maximal independent sets of vertices? (b) all minimal vertex covers (sets that hit every edge)?

Verified: yes
Solve time: 1m56s

Let $G=(V,E)$. Recall that a set $S\subseteq V$ is an independent set if no edge of $E$ has both endpoints in $S$. It is maximal independent if it is not properly contained in any other independent set. A set $C\subseteq V$ is a vertex cover if every edge of $E$ has at least one endpoint in $C$, and it is minimal if no proper subset is still a vertex cover.

Let $T$ denote the algorithm of Exercise 132, which generates all maximal solutions of a hereditary constraint system by systematic backtracking: it extends a partial set while maintaining feasibility and outputs a solution precisely when it is maximal with respect to inclusion.

(a) All maximal independent sets

We apply algorithm $T$ to the ground set $V$ with the feasibility predicate

$$ P(S) \equiv \text{``}S \text{ is an independent set in } G\text{''}. $$

The key property is that independence is downward closed: if $S$ is independent then every subset of $S$ is independent. This makes it suitable for the maximal-solution enumeration framework of Exercise 132.

Algorithm $T$ is run with the rule that a vertex $v\in V$ may be added to the current partial solution $S$ only if $S\cup{v}$ remains independent, that is, $v$ is not adjacent to any vertex already in $S$. The backtracking explores all inclusion-wise maximal ways to build such sets. When the algorithm reaches a state where no additional vertex can be added without violating independence, the current set is output. By construction, these outputs are exactly the maximal independent sets of $G$, since every independent set that is not maximal can still be extended, and every maximal one is reached and output once.

Thus, Exercise 132 applied with predicate $P$ enumerates all maximal independent sets.

(b) All minimal vertex covers

We use the standard complement relationship between independent sets and vertex covers. For any $S\subseteq V$, let $C=V\setminus S$. Then:

$$ S \text{ is independent} \quad \Longleftrightarrow \quad C \text{ is a vertex cover}. $$

Moreover, maximality and minimality are dual under complement:

$$ S \text{ is a maximal independent set} \quad \Longleftrightarrow \quad V\setminus S \text{ is a minimal vertex cover}. $$

Indeed, if $S$ is maximal independent and we remove a vertex from $C=V\setminus S$, then we add it to $S$, contradicting maximality unless independence is violated; equivalently, every vertex in $C$ is necessary to cover some edge not covered by $C\setminus{v}$.

Therefore, to find all minimal vertex covers, we first use algorithm $T$ as in part (a) to enumerate all maximal independent sets $S$, and then output their complements $V\setminus S$. This produces exactly all minimal vertex covers of $G$, each once.

Hence Exercise 132 yields minimal vertex covers via complementation of the maximal independent sets generated in part (a).