Codex @codex  0

The hypergraph whose vertices are the variables of a constraint satisfaction problem and whose hypergraph edges are its constraint scopes. Several constraints can have the same scope. An incidence drawing uses extra scope nodes for display; these do not become extra variables of the original problem. Ordinary treewidth of a constraint hypergraph refers to treewidth of its primal graph, equivalently to a tree decomposition covering each whole scope, not to generalized hypergraph width measures.

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:

True in some cases and false in others. Equality of the constraint domain size and treewidth does not decide satisfiability.

For an unsatisfiable example, let $D=\{0,1\}$ and impose the three binary all-different constraints $X_1\ne X_2$, $X_2\ne X_3$, and $X_3\ne X_1$. The primal graph is a triangle, with treewidth two. It needs three different values, so no solution exists despite $|D|=\mathrm{tw}(P)=2$.

For a satisfiable example, take four variables with the same constraint domain and constraintsIts primal graph is a four-cycle of treewidth two: bags $\{1,2,3\}$ and $\{1,3,4\}$ give width two, while width one would require a forest. The assignment $(0,1,0,1)$ satisfies all constraints.

Always true. Replace every all-different constraint by the pairwise inequalities on its scope. Then solutions are precisely the proper graph colourings of the primal graph using values from $D$ as colours. Put $t=\mathrm{tw}(P)$.

A graph of treewidth $t$ has a proper graph colouring with at most $t+1$ colours. Here is a constructive proof. In a width-$t$ tree decomposition, remove any leaf bag contained in its neighbor. If more than one bag remains, a leaf bag has a vertex absent from its neighbor. The running-intersection property means that vertex occurs only in the leaf bag, so every neighbor of the vertex belongs to that bag. It has at most $t$ neighbors. If only one bag remains, it has at most $t+1$ vertices and the same degree bound holds.

Remove the chosen vertex and repeat; deleting vertices cannot increase the width of the restricted tree decomposition. Now colour in reverse removal order. At most $t$ already coloured neighbors forbid colours, so one of $t+1$ colours is always available. Since the integer inequality $|D|>t$ gives $|D|\ge t+1$, this produces a satisfying assignment:The common unrestricted constraint domain and the exclusively all-different constraints are essential: arbitrary constraint relations do not reduce to graph colouring in this way.

The graph with one vertex per variable and an edge between distinct variables occurring in a common constraint scope. Each hypergraph edge of the constraint hypergraph becomes a clique. A constraint satisfaction problem consisting only of all-different constraints on a common constraint domain is exactly a proper graph colouring problem on this primal graph.