Past exam of the computer science course of the University of Oxford / 2015 / Intelligent systems / 3 / b

Choose the distinct values of $(X_1,X_2,X_4)$ and call them $(a,b,c)$. There are $3!=6$ choices. Constraint (5), on $(X_1,X_4,X_9)$, immediately forces $X_9=b$.

Constraints (2) and (3) require $X_5\ne X_2=b$ and $X_5\ne X_4=c$, respectively. Since the constraint domain has exactly three values, $X_5=a$. Constraint (2) now forces $X_3=c$, and constraint (3) forces $X_6=b$. Finally, constraint (4) permits $(X_7,X_8)=(a,c)$ or $(c,a)$.

Every choice just described satisfies all five all-different constraints, and the forced-value argument shows there are no other possibilities. HenceIn the order $(X_1,\dots ,X_9)$, the two forms arewhere $(a,b,c)$ ranges over the six permutations of $(0,1,2)$.

The constraint hypergraph has one vertex for each of $X_1,\dots ,X_9$ and one hypergraph edge for each constraint scope:Here $i$ abbreviates $X_i$. These five scopes follow the corrected source.^[ref] The diagram uses the incidence representation: round nodes are the original variables, square nodes represent hypergraph edges, and a joining line means that the variable belongs to that constraint scope. The square nodes are not extra variables of $P$.

In particular, the central pattern involving $X_2,X_4,X_5$ forms a cycle through three constraint scopes; the scopes cannot themselves simply be joined into a valid tree decomposition without an additional bag.

Use the ordinary treewidth of the primal graph of the constraint hypergraph: two variables are adjacent whenever they occur together in an all-different constraint. Equivalently, a tree decomposition of this constraint hypergraph has a bag containing every constraint scope, together with the running-intersection requirement for each variable. This is distinct from taking the treewidth of its incidence drawing.

Introduce a central bag $B_0=\{2,4,5\}$ and the five scope bagsJoin $B_0$ to each of $B_1,B_2,B_3$, join $B_3$ to $B_4$, and join $B_1$ to $B_5$:

Every constraint scope is contained in its own bag, and every variable occurs. The nontrivial running-intersection checks are: $2$ occurs along $B_1-B_0-B_2$; $4$ along the connected branches $B_5-B_1-B_0-B_3$; $5$ along $B_2-B_0-B_3$; $1$ along $B_1-B_5$; and $6$ along $B_3-B_4$. Each of the other variables occurs in just one bag. This is therefore a valid tree decomposition of width $3-1=2$.

Conversely, any of the original three-variable constraint scopes forms a clique of size three in the primal graph. Such a clique must be contained in one bag of every tree decomposition, forcing width at least two. The upper and lower bounds agree: