TAOCP 7.2.2.1 Exercise 261

Section 7.2.2.1: Dancing Links

Exercise 261. ▶ [23] [23] Let $G$ be a directed acyclic graph, with source vertices $S$ and sink vertices $T$. a) Use Algorithm C (or Z) to find all sets of $m$ vertex-disjoint paths from $S$ to $T$. b) Also find all such sets of paths from $s_k$ to $t_k$ for $1 \le k \le m$, given $s_k$ and $t_k$. c) Apply (a) to find all sets of $n-1$ disjoint paths that enter an $n \times n$ square at the north or east edge, proceed by south and/or west steps, and exit at the south or west edge, avoiding the corners. (A random $16 \times 16$ example is shown.)

d) Apply (b) to find all vertex-disjoint, downward paths of eight knights that start on the top row of a chessboard and end on the bottom row in reverse order.

Verified: no
Solve time: 2m23s

Solution

Let $G=(V,E)$ be a directed acyclic graph, let $S \subseteq V$ be the set of sources and $T \subseteq V$ the set of sinks. A set of $m$ vertex-disjoint $S$–$T$ paths is a collection of directed paths $P_1,\dots,P_m$ such that each $P_k$ starts in $S$, ends in $T$, and no vertex of $V$ lies on two distinct paths.

The construction is expressed in the language of Algorithm C (or Z) as a generalized exact cover instance in which some items are mandatory and others are optional in the sense of Section 7.2.2.1. Each directed $S$–$T$ path $P$ in $G$ is treated as an option. The option $P$ consists of all vertices on the path, written as a set of items

$$ O(P)={v \in V : v \text{ lies on } P}. $$

Vertex-disjointness of chosen paths is enforced by the exact-cover rule that no item may be covered more than once among the selected options.

In order to enforce that exactly $m$ paths are chosen, introduce $m$ additional items $k_1,\dots,k_m$ called selection markers. For every $S$–$T$ path $P$ and every index $k$ with $1 \le k \le m$, create an option

$$ O(P,k)=O(P)\cup {k}. $$

Selecting an exact cover in which each marker $k$ is covered exactly once forces the selection of exactly $m$ paths, one per marker. Since each vertex item is covered at most once, the selected paths are vertex-disjoint.

The resulting exact cover instance has item set $V \cup {k_1,\dots,k_m}$ and option set ${O(P,k)}$. Applying Algorithm C or Z enumerates all solutions, each corresponding to an ordered assignment of $m$ vertex-disjoint $S$–$T$ paths.

Part (b) introduces prescribed endpoint pairs $(s_k,t_k)$ for $1 \le k \le m$. In this case, the construction is identical except that each option is restricted to paths $P_k$ that begin at $s_k$ and end at $t_k$, and the marker $k$ is attached only to such paths:

$$ O(P_k,k)=O(P_k)\cup {k}, \quad P_k:s_k \leadsto t_k. $$

Exact cover of the marker items forces exactly one path for each prescribed pair, and vertex items enforce disjointness.

For part (c), the $n \times n$ grid is interpreted as a DAG in which vertices are grid points except the four corners, and directed edges correspond to unit steps south or west. The sources are the north and east boundary vertices, and the sinks are the south and west boundary vertices. A path in this graph corresponds to a monotone route that avoids forbidden corners. Each such route is an option; selecting $n-1$ vertex-disjoint routes corresponds to choosing $n-1$ options whose vertex sets are disjoint and whose union covers all interior vertices exactly once. Algorithm C or Z generates all such families of routes by the same construction as in part (a) with $m=n-1$.

For part (d), each knight move in a fixed downward direction defines edges in a directed acyclic graph whose vertices are the squares of the chessboard. Sources are the squares in the top row, sinks are those in the bottom row in reverse order. Each complete downward knight path from a top-row square to its assigned bottom-row target is an option. The items are the board squares, and each option covers the squares visited by the corresponding knight path. The construction from part (b) with $m=8$ and prescribed pairings between top-row and bottom-row squares produces an exact cover instance whose solutions are precisely the vertex-disjoint collections of eight such knight paths.

This completes the reduction of all cases to Algorithm C or Z via exact cover encoding with selection markers. ∎