Past exam of the computer science course of the University of Oxford / 2021 / Artificial intelligence / 2

The audience assumptions are part of the constraint satisfaction problem. Talks occupy whole common-length slots, room capacity and travel times impose no additional restrictions, and different CS year cohorts do not overlap. Physics attendees are treated as separate from those cohorts and the Head of Department. To protect possible society overlaps, assume society members occur in each relevant student cohort and that the Head of Department may also need to attend $E$. No additional overlap between otherwise distinct audience groups is assumed. These are declared modelling choices, rather than claims about the actual membership of any group.

The shared-audience restrictions give the edge pairsFor example, the Head of Department's three introductions produce all three pairwise inequalities on $A,B,G$; the Physics audience gives $D\ne F$. The possible society overlaps addTogether these thirteen inequalities and $X_A=1$ give a binary formulation. There is no need for an all-different constraint on all seven variables: compatible talks may run in parallel. At least two rooms suffice for the solution below.

If the Head of Department is stipulated not to attend $E$, remove just $EA$; the exhibited schedule remains valid. If actual society membership excludes a specified cohort, remove its corresponding additional conflicts too. This separation makes clear which restrictions are direct requirements and which protect assumed overlapping attendance.

The constraint graph has vertices $A,B,C,D,E,F,G$ and the thirteen edges listed in (a). The following original drawing distinguishes named shared-audience edges from the additional society-overlap edges. Vertex colours show one valid slot assignment; they are not extra constraints.

The unary restriction $X_A=1$ is a constraint domain restriction and adds no edge. For reference, $E$ is adjacent to every other vertex; among the remaining vertices there is a triangle $ABG$, a cycle $BDFG$, and the edge $CD$.

A solution is $(A,B,C,D,E,F,G)=(1,2,1,3,4,2,3)$. Here is a backtracking search with forward checking, listing the chosen value order rather than assuming ascending values. No backtrack is needed on this branch.

Start with the constraint domains in (a). Assign $A=1$; remove $1$ from $B,G,E$. Choose $E=4$; remove $4$ from each remaining neighbour. Now $B,G$ both have domain $\{2,3\}$ and $C,D,F$ each have $\{1,2,3\}$. Choose $B=2$. Its inequality removes $2$ from $G$, forcing $G=3$, and also removes $2$ from $D$, leaving $D\in \{1,3\}$. Assigning $G=3$ removes $3$ from $F$, leaving $F\in \{1,2\}$.

Choose $D=3$. The edge $DC$ reduces $C$ to $\{1,2\}$; $DF$ makes no further deletion because $3$ is already absent from $F$. Choose $F=2$ and then $C=1$. All variables are assigned, and every constrained pair has different values.

In time order, the schedule is

The Head of Department attends slots $1,2,3$ for $A,B,G$; first-year attendees see $C,D$ in slots $1,3$; second-year attendees see $F,G$ in $2,3$; the third-year Keble group sees $B,D$ in $2,3$; Physics attendees see $D,F$ in $3,2$. Slot $4$ is free of every competing talk, so all assumed society overlaps are respected.

A tree decomposition of width $3$ has bagswith tree edges $K_1{K}_2$, $K_2{K}_3$, $K_2{K}_4$.

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.

This is a graph colouring constraint satisfaction problem, with four available colours and one fixed colour. Interpret slot labels as colours. Every conflict edge requires distinct endpoint colours, exactly as in proper graph colouring; independent sets of vertices can share a slot. The unary restriction on $A$ fixes its colour to $1$.

The lecture's 3-colouring problem is the same construction with domains $\{1,2,3\}$. For the present graph under the assumptions in (a), the clique $\{A,B,E,G\}$ prevents a 3-colouring, while (c) supplies a 4-colouring. The fixed colour on $A$ does not otherwise change existence, since an unconstrained colouring can have its colour names permuted to put $A$ in colour $1$.

This four-colour necessity is conditional on the explicit $EA$ overlap. Removing that one edge permits, for example, the 3-colouring $(A,B,C,D,E,F,G)=(1,2,2,3,1,2,3)$; the four-slot schedule remains valid in either model. Thus attendee modelling, rather than the mere availability of four slots, determines the required number of colours.

There is exactly one solution: $X_i=i$ for $i=1,\dots ,n$. Strict increase makes all $n$ values distinct. Since all lie in the $n$-element domain $\{1,\dots ,n\}$, they must use every value, and their increasing order fixes their positions.

Equivalently, $X_i\ge i$ by propagation from the lower endpoint, and $X_i\le i$ by propagating backwards from $X_n\le n$. For general $m\ge n$, choosing any $n$-element subset determines one increasing solution, giving the binomial coefficient $\left(\genfrac{}{}{0ex}{}{m}{n}\right)$; the case $m=n$ gives $1$.

Choose one global direction and impose it on every adjacent pair. Keep $X_i\in \{1,\dots ,m\}$, introduce $D\in \{+,-\}$, and impose for each $i<n$ the relationBecause the same $D$ occurs everywhere, transitivity gives either a strictly increasing whole sequence or a strictly decreasing one. Choosing independently between $<$ and $>$ at each edge would merely require adjacent values to differ and would incorrectly allow zigzags.

If a binary formulation is required, replace each ternary relation by a hidden-variable encoding. Add a variable $Y_i$ with domainUse three binary constraints: the sign component of $Y_i$ equals $D$, its first numeric component equals $X_i$, and its second equals $X_{i+1}$. These enforce exactly the relation above while leaving the original variable domains unchanged. Each auxiliary domain has $m(m-1)$ values.

For $n\ge 2$, the projected solutions in the original $X_i$ variables number $2\left(\genfrac{}{}{0ex}{}{m}{n}\right)$ when $m\ge n$, and zero otherwise. In particular $m=n=3$ gives exactly $(1,2,3)$ and $(3,2,1)$. For $n=1$, direction is irrelevant and the projected solutions number $m$, not $2m$.