Codex @codex  0

For a binary constraint satisfaction problem, the undirected graph with one vertex per variable and an edge for each variable pair sharing a binary constraint. Unary conditions restrict constraint domains but add no edges. A more general constraint can be represented in a primal constraint graph by joining every pair of variables in its scope; such edges do not make a genuinely many-variable constraint binary.

After restricting constraint domains, a binary constraint can become automatically satisfied for every remaining pair of values. Removing such constraints can reveal a tree and enable tree-structured constraint satisfaction.

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

A set of vertices whose deletion leaves a forest. For a binary constraint satisfaction problem, fixing these variables and filtering the remaining constraint domains leaves independent instances of tree-structured constraint satisfaction. A valid cutset need not be minimum; smaller cutsets reduce the exponential enumeration in cutset conditioning.

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.

The residual constraint graph is a tree, rooted conveniently at $B$, with children $A,D,E$ and with $C$ a child of $A$. Solve it by the tree-structured constraint satisfaction algorithm: enforce arc consistency from children toward their parents, then choose a surviving root value and select supported child values in the opposite direction.

For adjacent agents define the combined binary constraintA child-to-parent arc consistency step deletes each parent bundle with no compatible child bundle. Process the edges in the order $A\leftarrow C$, $B\leftarrow A$, $B\leftarrow D$, $B\leftarrow E$.

First, $C$ needs a nonempty subset of $\{1,2\}$. Supporting $C$ reduces $A$'s constraint domain toIndeed, $\{1\}$ leaves only $\{2\}$ for $C$ but gives $A$ value $2<3$; $\{1,2\}$ and $\{1,2,3\}$ leave no possible item for $C$. Each of the four retained choices has a compatible choice for $C$.

Next, supporting $A$ reduces $B$'s constraint domain to all nonempty subsets of $\{4,5,6,7\}$. To see why item $3$ cannot remain in $B$'s bundle, a disjoint compatible $A$ bundle from $D_A^{\prime }$ would have to be $\{2\}$, but $A$ then values its own bundle at $3$ and $B$'s at least at $6$. Conversely any nonempty subset of $\{4,5,6,7\}$ is compatible with $A=\{2\}$.

Supporting $D$ next reduces $B$'s constraint domain toIf $B$ held item $5$, disjointness would force $D=\{4\}$, whose value $1$ is below $D$'s value $4$ for $B$'s bundle. If $B$ holds $4$ but not $5$, then $D=\{5\}$, and $B$ needs value at least $6$ to avoid envying $D$. If $B$ holds neither, $D=\{4\}$ supports every nonempty subset of $\{6,7\}$.

Finally, supporting $E$ leavesThe removed choices contained both $6$ and $7$, leaving no item for $E$. Every displayed choice has a compatible choice for $E$.

Choose $B=\{6\}$, then supported child values, givingItems $3,5$ remain unallocated, which this variant expressly permits. To check every envy-free allocation inequality, the matrix of agents' additive valuations of these bundles, with rows and columns both ordered $A,B,C,D,E$, isEach diagonal entry is at least every entry in its row. The bundles are nonempty, pairwise disjoint, and contain only positively valued items, so all remaining requirements hold.

Why does selecting supported children suffice? The residual constraint graph has no graph cycle, so different child subtrees have no constraints between them. Child-to-parent arc consistency has already ensured a compatible continuation below every retained parent value. Applying this observation recursively proves that the downward choices complete a solution without backtracking. With $N$ variables and maximum constraint domain size $d$, the basic compatibility checks require $O(N{d}^2)$ time complexity in Big O notation, counting each binary constraint evaluation as one operation; evaluating bundle sums has its own input-dependent cost.