Lemma 14. The problem $1 \mid k_j, \mathrm{rep} \mid \min_j \sum_i Z_{i,j}$ is NP-hard even when the overall conflict graph has treewidth at most $4$.

Let $G$ be an instance of Multicoloured Independent Set in normal form: $r$-regular with $r \ge 1$, $\ell$ classes $V_1, \ldots, V_\ell$ of $n \ge 4$ vertices, and an even number $|E|$ of edges, every edge directed from the smaller class to the larger. The constructed instance has $\ell(n+1) + |E|$ days — for every colour $n$ vertex days and one validation day, and one edge day per edge — and the clients: a vertex client $c_v$ with $k_{c_v} = 1$ for every vertex; a selection client $c_i$ with $k_{c_i} = 1$ for every colour; two edge clients $c_{v,u}$ and $c_{u,v}$ with parameter $1$ for every edge $(v,u)$; two interaction clients $c^+$ and $c^-$ with $k^+ = k^- = |E|/2$; and a dummy client $c_0$ with $k_0 = \ell(n+1) + |E|$.

For every colour the vertex days and the validation day form a vertex-selection gadget which compels the selection of a single vertex client for that colour, and the edge days form an incidence-checking gadget which certifies that all clients can be satisfied only if the selected vertices form a multicoloured independent set. On each day only a few clients take part in the gadget, and the job of $c_0$ blocks the jobs of all the others: it starts right after the last job of the gadget, and every client not taking part has a unit-length job of its own inside it. Writing $N$ for the number of clients other than $c_0$ and $\pi$ for a bijection between them and $\{1, \ldots, N\}$, the job of $c_0$ has processing time $N$, and the job of such a client $c$ occupies the $\pi(c)$'th time unit of it. On the vertex day of a vertex $v$, the clients $c_v$ and $c_i$ of $v$'s colour have due date $r$ and processing time $r$, the job of $c_0$ has due date $r + N$, and every other client $c$ has due date $r + \pi(c)$ and processing time $1$. On the validation day of colour $i$, the client of the $p$'th vertex of $V_i$ has due date $rp$ and processing time $r$, the client $c_{v,u}$ of the $q$'th neighbour $u$ of that vertex has due date $r(p-1) + q$ and processing time $1$, the job of $c_0$ has due date $rn + N$, and every other client has due date $rn + \pi(c)$ and processing time $1$. On the edge day of an edge $(v,u)$, the client $c^-$ has due date $2$ and processing time $2$, $c^+$ due date $3$ and processing time $2$, $c_{v,u}$ due date $3$ and processing time $1$, $c_{u,v}$ due date $1$ and processing time $1$, the job of $c_0$ due date $3 + N$, and every other client due date $3 + \pi(c)$ and processing time $1$.

The overall conflict graph of the constructed instance has a tree decomposition of width four: a root bag $\{c_0, c^+, c^-\}$, a bag $\{c_0, c^+, c^-, c_i\}$ per colour below it, a bag $\{c_0, c^+, c^-, c_v, c_i\}$ per vertex of that colour below that, and a bag $\{c_0, c^+, c^-, c_v, c_{v,u}\}$ per neighbour $u$ of $v$ below that.