= 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(Nd^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.
Back to article page
