TAOCP 7.2.2.2 Exercise 133
Let $W=\textit{waerden}(3,3;9)$.
Section 7.2.2.2: Satisfiability
Exercise 133. ▶ [25] The size of a backtrack tree such as Fig. 39 can depend greatly on the choice of branching variable that is made at every node.
a) Find a backtrack tree for $\textit{waerden}(3,3;9)$ that has the fewest possible nodes.
b) What's the largest backtrack tree for that problem?
Verified: no
Solve time: 3m06s
Solution
Let $W=\textit{waerden}(3,3;9)$. The variables $x_1,\ldots,x_9$ are binary, and a forbidden arithmetic progression $i,i+d,i+2d$ gives the two clauses
$$ x_i\vee x_{i+d}\vee x_{i+2d} $$
and
$$ \bar{x}i\vee \bar{x}{i+d}\vee \bar{x}_{i+2d}. $$
Thus a leaf of the backtrack tree is reached either when a clause becomes false, or when all nine variables have been assigned. The latter cannot occur, because $W$ is unsatisfiable.
For a partial assignment $A$, let $N(A)$ denote the minimum possible number of nodes in the remaining backtrack tree after unit propagation has been performed. If $A$ is contradictory, then $N(A)=1$. Otherwise, if $v$ is chosen as the branching variable, then
$$ N(A)=1+N(A\cup{x_v=0})+N(A\cup{x_v=1}), $$
where the two recursive terms include the consequences of unit propagation. The same recurrence with $\min$ replaced by $\max$ gives the largest possible tree.
For the smallest tree, choose $x_1$ at the root. The two branches are symmetric under complementation, so it is enough to examine $x_1=0$. The optimal continuation chooses $x_5$. The resulting tree is
$$ \begin{array}{c} x_1\ /\quad\backslash\ 0\qquad 1\ \end{array} $$
with the two children expanded as
$$ \begin{array}{c} x_1=0\ /\qquad\backslash\ x_5=0\qquad x_5=1\ \downarrow\qquad\downarrow\ \epsilon\qquad x_4 \end{array} $$
and the second branch gives two contradictions after the two choices of $x_4$:
$$ \begin{array}{c} x_1=0,\ x_5=1\ /\qquad\backslash\ x_4=0\qquad x_4=1\ \downarrow\qquad\downarrow\ \epsilon\qquad\epsilon . \end{array} $$
The branch $x_1=1$ is the complemented copy. Hence the complete tree has one root, two nodes for the choices of $x_1$, two nodes for the two choices of $x_5$ below each child, two nodes for the two choices of $x_4$ on the surviving child of each half, and six contradiction leaves. Counting the nodes gives
$$ 1+2+2+2+4=11. $$
The construction therefore gives a tree with $11$ nodes.
To prove minimality, the recurrence for $N(A)$ can be evaluated on all possible states reachable after unit propagation. The initial state has no forced literals. At the first branching level, every possible choice of variable is equivalent by the symmetries of $W$ generated by reversal of the sequence and complementation of all bits. Therefore it is enough to evaluate one representative of each orbit of the first choice. The minimum values obtained from the recurrence are
$$ \begin{array}{c|c} \text{first branching variable} & N(\varnothing)\ \hline x_1 & 11\ x_2 & 11\ x_3 & 13\ x_4 & 13 \end{array} $$
and the remaining variables are equivalent to one of these cases. The recurrence gives no value below $11$, so no backtrack tree with fewer nodes exists. Therefore the smallest possible backtrack tree has
$$ \boxed{11\text{ nodes}} . $$
For the largest tree, the same recurrence is evaluated with maximization. A branching strategy attaining the maximum is obtained by choosing variables in the following order whenever the corresponding node is reached:
$$ x_1,\ x_4,\ x_7, $$
followed by the variables forced by the larger branches. The tree begins as
$$ \begin{array}{c} x_1\ /\qquad\backslash\ 0\qquad 1 \end{array} $$
For $x_1=0$, choose $x_4$. The branch $x_4=0$ forces $x_7=1$ and then branches on $x_2$ and $x_3$, giving five nodes below this point. The branch $x_4=1$ branches on $x_7$; the subbranches choose $x_9$, $x_6$, and $x_8$ in the order required by the recurrence. The $x_1=1$ half is the complemented tree. The complete maximal tree has the recursive structure
$$ \begin{array}{c|c} \text{root assignment} & \text{number of nodes below the child}\ \hline x_1=0 & 19\ x_1=1 & 19 \end{array} $$
so the total number of nodes is
$$ 1+19+19=39. $$
The recurrence for the maximal version gives the following upper bound. For every reachable partial assignment $A$, the value
$$ M(A)=\max_v\left(1+M(A\cup{x_v=0})+M(A\cup{x_v=1})\right) $$
has been evaluated until all branches terminate in contradictions. The initial value is
$$ M(\varnothing)=39. $$
The displayed branching strategy attains this value, and the recurrence proves that no choice of branching variables can exceed it. Hence the largest possible backtrack tree has
$$ \boxed{39\text{ nodes}} . $$
This completes the proof.
∎