TAOCP 7.2.2.2 Exercise 453
In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values.
Section 7.2.2.2: Satisfiability
Exercise 453. [M23] $[M23]$ An $m \times n$ matrix $X = {x_{ij}}$ is said to be decomposable if it has row indices $R \subseteq {1, \ldots, m}$ and column indices $C \subseteq {1, \ldots, n}$ such that $0 < |R| + |C| < m + n$, with $x_{ij} = 0$ whenever $(i \in R$ and $j \notin C)$ or $(i \notin R$ and $j \in C)$. It represents a bipartite graph on the vertices ${u_1, \ldots, u_m}$ and ${v_1, \ldots, v_n}$, if $|u_i - v_j| = [x_{ij} \ne 0]$. a) Prove that $X$ is indecomposable if and only if its bipartite graph is connected. b) The direct sum $X' \oplus X''$ of matrices $X'$ and $X''$, where $X'$ is $m' \times n'$ and $X''$ is $m'' \times n''$, is the $(m' + m'') \times (n' + n'')$ "block diagonal" matrix $X$ that has $X'$ in its upper left corner, $X''$ in the lower right corner, and zeros elsewhere (see 7-(40)). True or false: If the rows and columns of $X'$ and $X''$ are nonnegative and lexicographically ordered as in (185) and (186), so are the rows and columns of $X$. c) Let $X$ be any nonnegative matrix whose rows and columns are lexicographically nondecreasing, as in (185) and (186). True or false: $X$ is decomposable if and only if $X$ is a direct sum of smaller matrices $X'$ and $X''$.
Verified: no
Solve time: 6m02s
Solution
In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write
$$ x_{i,j}=1\iff x_i=j, $$
where $0\le i<p$ and $1\le j\le d$ if the domain has size $d$. The direct encoding already contains the clauses forcing each $x_i$ to have exactly one value. The all-different constraint adds the requirement that two different variables cannot choose the same value.
For two distinct variables $x_i$ and $x_k$, and for any value $j$, the assignment
$$ x_{i,j}=x_{k,j}=1 $$
must be forbidden. The corresponding clause is
$$ \bar{x}{i,j}\vee \bar{x}{k,j}. $$
Taking all pairs of variables and all possible values gives the complete encoding:
$$ \bigwedge_{0\le i<k<p}\ \bigwedge_{1\le j\le d} (\bar{x}{i,j}\vee\bar{x}{k,j}). $$
These clauses are sufficient. Suppose the direct variables represent an assignment satisfying the clauses. If two variables $x_i$ and $x_k$ had the same value $j$, then the direct encoding would require
$$ x_{i,j}=1,\qquad x_{k,j}=1. $$
The clause
$$ \bar{x}{i,j}\vee\bar{x}{k,j} $$
would then be false, contradicting satisfiability. Hence no two variables receive the same value.
They are also necessary. Given any assignment satisfying the all-different constraint, no pair of variables $x_i,x_k$ has the same value. Therefore, for every $j$, at least one of $x_{i,j}$ and $x_{k,j}$ is false, so every clause
$$ \bar{x}{i,j}\vee\bar{x}{k,j} $$
is satisfied.
Thus the all-different constraint in the direct encoding is enforced by adding one binary clause for every pair of variables and every possible value:
$$ \boxed{\bar{x}{i,j}\vee\bar{x}{k,j}\qquad (0\le i<k<p,\ 1\le j\le d).} $$
This completes the proof. ∎