TAOCP 7.2.2.1 Exercise 209

Section 7.2.2.1: Dancing Links

Exercise 209. [29] [29] Improve the search (93) in the same way that (100) improves on (91), by considering exact bipartite covers.

Verified: yes
Solve time: 1m30s

Setup

Let the instance of the exact cover problem consist of a set of items $I$, partitioned into two disjoint classes $I = U \cup V$, $U \cap V = \varnothing$, together with a family of options $\mathcal{O}$. In an exact bipartite cover, each option $O \in \mathcal{O}$ contains exactly one item of $U$ and exactly one item of $V$.

Thus each option has the form

$$ O = {u, v}, \quad u \in U,\ v \in V. $$

Let $E \subseteq U \times V$ be the set of pairs corresponding to options, so that $(u,v) \in E$ if and only if ${u,v} \in \mathcal{O}$. The problem is to select a subset $M \subseteq E$ such that every item of $U \cup V$ occurs in exactly one selected pair. This is a perfect matching formulation.

Search (93) applies Algorithm X in its general form: at each level it selects an item $i$, branches over options containing $i$, and recursively covers all other items in each option.

The task is to improve this search in the same spirit that (100) improves (91), by exploiting the bipartite structure so that branching occurs on pairs rather than general multi-item options.

Solution

In the general Algorithm X search (93), a choice is made by selecting an uncovered item $i$, then iterating over each option $O$ containing $i$. For each such $O$, all items in $O$ are covered sequentially, producing a residual instance.

In the bipartite setting, each option $O$ contains exactly two items, one in $U$ and one in $V$. This permits a symmetric reformulation in which the branching step selects an edge $(u,v)$ directly rather than selecting an item and then enumerating incident options.

Let $u \in U$ be an uncovered item. Define its neighbor set

$$ N(u) = { v \in V : (u,v) \in E }. $$

Each candidate option containing $u$ corresponds uniquely to a choice of $v \in N(u)$.

The improved search replaces the item-driven branching by the following symmetric step.

Select an uncovered item $x$ from $U \cup V$ of minimum degree, where the degree is computed in the bipartite graph:

$$ \deg(u) = |N(u)|,\quad \deg(v) = |{u \in U : (u,v) \in E}|. $$

Assume without loss of generality that $x \in U$. For each $v \in N(x)$, perform a single combined covering operation corresponding to the option $(x,v)$:

Cover both items $x$ and $v$ simultaneously. Since every option contains exactly two items, the covering of $(x,v)$ removes exactly one edge and eliminates all other edges incident to $x$ and $v$. Formally, define the residual instance by deleting:

$$ x,\ v,\ \text{and all edges incident to } x \text{ or } v. $$

The recursive call is then applied to the resulting reduced bipartite graph.

The crucial structural improvement over search (93) is that no intermediate enumeration over options containing $x$ is required beyond iterating over neighbors in $N(x)$, and no secondary inner loop over the remaining items of an option occurs, since each option has cardinality two. The covering operation for a chosen option reduces to a single matched pair removal.

This yields a symmetric branching rule:

Choose $x \in U \cup V$ minimizing degree.
For each neighbor $y$ of $x$, recursively solve the instance obtained by deleting both $x$ and $y$.

This reformulation improves search (93) by reducing each branching step to pure edge selection in a bipartite graph, eliminating the multi-item cascading cover step inherent in general options and thereby matching the structure of (100), which similarly collapses higher-order choices into more constrained combinatorial primitives when the incidence structure permits it.

Verification

Each option in the bipartite exact cover instance is of the form ${u,v}$ with $u \in U$ and $v \in V$. Selecting an option in Algorithm X corresponds exactly to choosing one such pair.

In the improved procedure, choosing a neighbor $v \in N(u)$ corresponds bijectively to selecting the option ${u,v}$, since the mapping between edges and options is one-to-one by definition of $E$.

Covering both $u$ and $v$ removes all options incident to either endpoint. Every option containing $u$ is removed because it uses $u$, and every option containing $v$ is removed because it uses $v$. No other option is affected except through shared endpoints, which is consistent with the exact cover constraint that no item may appear more than once.

Since each recursive step removes exactly one element from $U$ and one from $V$ whenever a pair is chosen, feasibility of the remaining instance is preserved, and any solution of the reduced instance extends uniquely to a solution of the original instance by reintroducing the chosen pair.

Thus the transformation preserves correctness and yields a search that enumerates exactly the same solution set as (93), while operating on edges rather than general options.

This completes the proof. ∎