Past exam of the computer science course of the University of Oxford / 2020 / Artificial intelligence / 2 / d

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.^[ref]

Here take $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 givesThe 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.