= Solution
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 bags
$$
B_1=\{1,2,4\},\quad B_2=\{2,3,5\},\quad B_3=\{4,5,6\},\quad
B_4=\{6,7,8\},\quad B_5=\{1,4,9\}.
$$
Join $B_0$ to each of $B_1,B_2,B_3$, join $B_3$ to $B_4$, and join $B_1$ to $B_5$:
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/intelligent-systems-2015-decomposition.png]
{title=A minimum-width tree decomposition with central bag containing variables 2, 4, and 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:
$$
\boxed{\operatorname{tw}(P)=2.}
$$
Back to article page
