= Cutset conditioning
Enumerate assignments to a <cycle cutset>, reject internal violations, filter all crossing <binary constraints>, and solve the residual <forest> by <tree-structured constraint satisfaction>. A full solution restricts to one enumerated cutset assignment; the residual tree passes preserve all its values. Conversely, a consistent cutset assignment combined with supported residual solutions satisfies every constraint. These observations prove completeness and soundness.
With $n$ <variables>, maximum <constraint domain> size $q$ and cutset size $k$, there are at most $q^k$ assignments and $O((n-k)q^2)$ residual tree work per assignment. Internal cutset and crossing-constraint tests require additional accounting. The method is attractive when a small <cycle cutset> is available.<CS 188 constraint ordering and structure notes>[§2.4.1, Structure, cutset conditioning]{ref}
Back to article page
