= Solution
<Cutset conditioning> selects a <cycle cutset> $C$: deleting its <vertices> makes the binary <constraint graph> a <forest>. Enumerate assignments to $C$, reject those violating internal constraints, and filter each remaining <constraint domain> against the chosen cutset values. Solve the residual components by <tree-structured constraint satisfaction>. Stop at a successful assignment, or report failure after all cutset assignments fail. Completeness follows by considering the restriction of any full solution to $C$; soundness follows by checking internal, crossing and residual constraints. With maximum <constraint domain> size $q$ and $k$ cutset <variables>, a typical bound is $O(q^k(n-k)q^2)$ for the residual <forest> work, with cutset and crossing checks added explicitly.<CS 188 constraint ordering and structure notes>[§2.4.1, tree passes and cutset conditioning]{ref}
Here take \b[$C=\{c,e\}$]. The residual <constraint graph> has <vertices> $a,b,d$ and only <edges> $ab,ad$, a <tree> rooted at $a$. Choose the consistent cutset values $c=3,e=1$. Filtering against these assignments gives
$$
D_a=\{1,2\},\quad D_b=\{2\},\quad D_d=\{2,4\}.
$$
The upward support pass from $b$ deletes $a=2$, because $b$ can only equal $2$. The pass from $d$ retains $a=1$, which has support $2$ or $4$. Assign $a=1$ at the root and then supported child values $b=2,d=2$. Together with $c=3,e=1$, this gives the solution in (c).
No singleton <cycle cutset> exists: deleting $a,b,d$ or $e$ leaves, respectively, a triangle on $bce,acd,abc$ or $abc$; deleting $c$ leaves the <cycle in a graph> $a-b-e-d-a$. Thus the two-element choice is also minimum, although the <algorithm> only requires a valid cutset.
Back to article page
