TAOCP 7.2.2.1 Exercise 438

Section 7.2.2.1: Dancing Links

Exercise 438. [30] Explain how to modify Algorithm C so that, when given an XCC problem from the construction in answer 437, it will produce only solutions that satisfy also the connectivity condition (iii). Hint: See exercise 413; also consider reachability.

Verified: no
Solve time: 4m17s

---

The previous solution failed because it attempted to introduce an additional pruning condition based on an informal notion of “forced black in all completions,” which is not a valid XCC-state predicate. The correct approach is to use only a monotone reachability invariant that is expressible directly in the current partial state of Algorithm C.

We now restart the argument and give a correct modification of Algorithm C.

1. Setup

Let $G = (V,E)$ be the grid graph of the Hitori instance obtained from Exercise 437. A solution corresponds to a set of black vertices $B \subseteq V$, and the white vertices are $W = V \setminus B$.

Conditions (i) and (ii) are already enforced by the XCC construction, so the only additional requirement is:

$$ \text{(iii) } G[W] \text{ is connected.} $$

Fix a distinguished root vertex $r \in V$ (for example, the lexicographically smallest cell). We impose the standard harmless normalization:

$$ r \in W \quad \text{(i.e., (r) is never black).} $$

This is safe because if a valid connected white set exists, it contains some vertex, and we can always choose that vertex as the root by symmetry of the grid construction.

2. Key monotone invariant (reachability)

At a node $S$ of Algorithm C, let $B(S)$ be the set of vertices already chosen black, and define the current available graph:

$$ G(S) = G - B(S). $$

Let $R(S)$ be the set of vertices reachable from $r$ in $G(S)$.

Monotonicity

If $S' \supseteq S$, then $G(S')$ is obtained from $G(S)$ by deleting more vertices, hence:

$$ R(S') \subseteq R(S). $$

Thus reachability can only shrink during the search.

3. Correct interpretation of connectivity

In any complete solution $B$, the white graph is:

$$ G[V \setminus B]. $$

Since only black vertices are removed during the search, we have:

$$ G[V \setminus B] = G(S) \quad \text{at completion}. $$

Therefore:

$$ G[V \setminus B] \text{ is connected} \quad \Longleftrightarrow \quad R(S) = V \setminus B. $$

So connectivity holds exactly when every vertex that is not black is reachable from $r$ in the final residual graph.

4. Correct modification of Algorithm C

We modify Algorithm C by adding a reachability forcing rule, not a heuristic pruning rule.

Modification

At any node $S$:

1. Compute $R(S)$, the vertices reachable from $r$ in $G(S)$.
2. If a vertex $v \in V$ satisfies:

$$ v \notin R(S), $$

then $v$ cannot be part of any connected white solution extending $S$.

Hence we must enforce:

$$ v \in B \quad \text{(force (v) to be black).} $$ 3. Therefore Algorithm C is modified as follows:

• If $v \notin R(S)$, immediately restrict the search to the branch where $v$ is chosen as black (i.e., select only columns of the XCC instance that include $v$ in the black set).
• If no such choice is compatible with constraints (i) and (ii), backtrack.

4. Continue Algorithm C normally with these forced choices added.
5. At completion, output the solution only if all constraints are satisfied (this is already guaranteed for (i) and (ii)).

5. Why this is correct

(i) Soundness

Every produced solution satisfies (i) and (ii) by the XCC construction.

For connectivity:

• If a vertex $v$ were white in the final solution but not reachable from $r$ in $G(S)$ at some stage, it would remain unreachable forever (monotonicity of reachability).
• The forcing rule prevents this situation by ensuring that every unreachable vertex is permanently blackened.

Thus every remaining white vertex in a complete solution lies in $R(S)$, so all white vertices are reachable from $r$, hence connected.

(ii) Completeness

Let $B^*$ be any valid solution satisfying (i), (ii), and (iii).

Since $G[V \setminus B^]$ is connected and contains $r$, every vertex $v \in V \setminus B^$ is reachable from $r$ in every partial graph along the search path consistent with $B^*$.

Hence:

$$ v \in R(S) \quad \text{for every prefix } S \subseteq B^*. $$

So the forcing rule never incorrectly forces a vertex of $V \setminus B^$ to be black, and the branch corresponding to $B^$ is never pruned.

Therefore Algorithm C still reaches every valid solution.

6. Conclusion

The correct modification of Algorithm C is not a post-hoc connectivity check and not an ill-defined pruning heuristic.

It is the addition of a single monotone forcing invariant:

Any vertex that is no longer reachable from a fixed root in the current residual graph must be forced to be black immediately.

This ensures that every completed solution has all remaining white vertices in the reachable region of the root, and therefore satisfies connectivity condition (iii), while preserving completeness of the search. ∎