= Solution
\b[A <tree decomposition> of width $3$ has bags]
$$
K_1=\{A,B,E,G\},\quad K_2=\{B,D,E,G\},\quad
K_3=\{D,E,F,G\},\quad K_4=\{C,D,E\},
$$
with <tree> <edges> $K_1K_2$, $K_2K_3$, $K_2K_4$.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2021/artificial-intelligence-schedule-decomposition.png]
{title=A tree decomposition of the scheduling graph with maximum bag size four}
Every <graph> <vertex> occurs in a bag and every constraint <edge> has both endpoints in some bag. The bags containing any fixed <vertex> form a connected <connected subgraph of a tree>: $B$ occurs in $K_1,K_2$, $G$ in $K_1,K_2,K_3$, $D$ in $K_2,K_3,K_4$, and $E$ in all four. The remaining <vertices> occur once. Hence the running-intersection condition holds. The maximum bag size is four, giving width $4-1=3$.
Under the stated overlap assumptions, $\{A,B,E,G\}$ is a four-<vertex> <clique>, so the <treewidth> is at least $3$; this decomposition attains it. A proof of that lower bound is not needed to use the displayed decomposition.
Back to article page
