 Tree-structured constraint satisfaction

A binary constraint satisfaction problem whose constraint graph is a tree. Restrict constraint domains by unary conditions first. Choose a rooted tree orientation and process children before parents. For each child $j$ of $i$, retain in $D_i$ only values having a compatible value in the already reduced $D_j$. Thus every retained parent value has support in each child subtree.

If the root constraint domain becomes empty, no solution exists. Otherwise choose any root value, then recursively choose supported child values. A child-to-parent arc consistency pass need not enforce full arc consistency in both directions; the chosen directional condition suffices for this construction.

The proof uses mathematical induction on subtrees. A retained leaf value satisfies its unary requirements. Each retained parent value has a supported value in every child subtree. Those subtree solutions can be combined because the tree has no edges between different child subtrees. Therefore every retained parent value extends to a whole subtree solution, and every retained root value extends to a complete solution without backtracking.

For $N$ variables and maximum constraint domain size $d$, scanning all value pairs once per edge costs $O(N{d}^2)$ time complexity in Big O notation, when one binary constraint evaluation has unit cost. If a constraint requires summing bundle values, its evaluation cost must also be counted.