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:

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.

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.