Proof. We prove the claim by a bottom up induction over \(\syntaxtree\).

For the base case, let \(x\) be an introduce node with \(\mu_x=i(v)\). Then \(G_x\) consists only of the vertex \(v\) with label \(i\). Hence there is exactly one feasible partition of \(V(G_x)\) into cliques of size at most \(d\), namely the partition containing the single clique \(\{v\}\). Therefore it holds that \(A_x^0[s]=1\) for the unique state \(s\in \states\) with \(s(\langle i\rangle)=1\) and \(s(M)=0\) for all other \(M\in \mathcal{M}_d\), and \(A_x^{\omega}[s']=0\) for all other pairs \((\omega,s')\). This matches the definition of \(T_x^{\omega}\) in the algorithm, and thus \(T_x^{\omega}=A_x^{\omega}\) for all \(\omega\in [n]_0\).

For the induction step, let \(x\) be a join node of \(\syntaxtree\), and assume that the statement holds for the children of \(x\). Let \(x_1\) and \(x_2\) be the children of \(x\), and let \((X_1,Y_1),\dots,(X_h,Y_h)\) be the ordered list of pairs of multisets used by the algorithm at node \(x\).

For each \(i\in [h]_0\) and each \(\omega\in [n]_0\), we define an auxiliary table \(A_i^{\omega}\in \{0,1\}^{\states^{2k}}\) as follows: Let \(G^i\) be the graph obtained from the shifted disjoint union of \(G_{x_1}\) and \(G_{x_2}\) by adding all edges between vertices of \(G_{x_1}\) with labels in \(X_j\) and vertices of \(G_{x_2}\) with labels in \(Y_j\) for each index \(j\in [i]\). Then for \(s\in \states^{2k}\) and \(\omega\in [n]_0\), we set \(A_i^{\omega}[s]=1\) if and only if there exists a partial solution in \(G^i\) of weight \(\omega\) and state \(s\).

We now prove by induction on \(i\in [h]_0\) that \(T_i^{\omega}=A_i^{\omega}\) for every \(\omega\in [n]_0\). For \(i=0\), no clique is allowed to use vertices from both sides. Hence a partition counted by \(A_0^{\omega}\) is exactly the disjoint union of a partition of \(G_{x_1}\) and a partition of \(G_{x_2}\), where the labels on the second side are shifted by \(k\). Thus \(A_0^{\omega}\) is obtained by combining the tables of the two children via the shifted union operation \(\punion\). By the induction hypothesis on the syntax tree, the child tables satisfy \(T_{x_1}^{\omega}=A_{x_1}^{\omega}\) and \(T_{x_2}^{\omega}=A_{x_2}^{\omega}\). It follows that \(T_0^{\omega}=A_0^{\omega}\) for every \(\omega\in [n]_0\).

Assume now that \(i\in [h]\) and that \(T_{i-1}^{\omega}=A_{i-1}^{\omega}\) holds for all \(\omega\in [n]_0\). We show that \(T_i^{\omega}=A_i^{\omega}\) for all \(\omega\in [n]_0\). First suppose that the pair \((X_i,Y_i)\) cannot form a clique across the join, either because \(|X_i\cup Y_i|\geq d+1\) or because some label occurring in \(X_i\) is not joined to some label occurring in \(Y_i\). Then processing the \(i\)-th pair creates no new cliques, so the family of partial solutions does not change: \(A_i^{\omega}=A_{i-1}^{\omega}\) for all \(\omega\). Since it holds in this case, that \(T_i^{\omega}=T_{i-1}^{\omega}\), the claim follows from the induction hypothesis.

Suppose therefore that \((X_i,Y_i)\) is feasible. If it holds that \(T_i^{\omega}[s]=1\), then, by the update rule of the algorithm, this value arises from some state \(s'\in \states^{2k}\) and some integer \(r'\in [\min\{s'(X_i),s'(Y_i)\}]_0\) with \(T_{i-1}^{\omega'}[s']=1\), where \(\omega'=\omega\) if \(|X_i\cup Y_i|\leq d-1\) and \(\omega'=\omega-r'\) if \(|X_i\cup Y_i|=d\). By the induction hypothesis for \(i-1\), there exists a packing counted by \(A_{i-1}^{\omega'}[s']\). In this packing we choose \(r'\) cliques of type \(X_i\) and \(r'\) cliques of type \(Y_i\) and merge them pairwise. Since \((X_i,Y_i)\) is feasible, each merge produces a clique with label multiset \(X_i\cup Y_i\); if \(|X_i\cup Y_i|=d\) then each such merge contributes one clique of size \(d\), and otherwise it contributes one incomplete clique of type \(X_i\cup Y_i\). Hence, it follows that \(A_i^{\omega}[s]=1\).

For the converse implication, assume that \(A_i^{\omega}[s] = 1\), and let \(\mathcal{P}\) be a partition of the vertices of the shifted disjoint union of \(G_{x_1}\) and \(G_{x_2}\) into cliques of size at most \(d\) that satisfies the three conditions in the definition of \(A_i^{\omega}\). Then \(\mathcal{P}\) results from a partition counted by \(A_{i-1}^{\omega'}[s']\) by merging \(r'\) pairs of cliques of type \(X_i\) and \(Y_i\) for some value \(r'\in [\min\{s'(X_i), s'(Y_i)\}]_0\), where \(\omega' = \omega\) if \(|X_i\cup Y_i|\leq d-1\) and \(\omega'=\omega-r'\) otherwise, and \(s'\) is the state obtained from \(s\) by subtracting \(r'\) from \(s(X_i\cup Y_i)\) and adding \(r'\) to \(s(X_i)\) and \(s(Y_i)\). By the induction hypothesis for \(i-1\), the algorithm sets \(T_{i-1}^{\omega'}[s']=1\). Since the description of \(s'\) and \(\omega'\) matches the update rule of the algorithm, it follows that \(T_i^{\omega}[s]=1\).

We now define the auxiliary table \(\hat{A}^{\omega}\in \{0,1\}^{\states^{2k}}\) as follows. Let \(\hat{G}\) be the graph resulting from the disjoint union of \(G_{x_1}\) and \(G_{x_2}\) by adding all edges as defined by \(\alpha\). Then \(\hat{A}^{\omega}[s]=1\) if and only if there exists a partial solution in \(\hat{G}\) of weight \(\omega\) and state \(s\). Clearly, \(\hat{G}\) results from \(G^h\) by applying the relabeling \(\gamma^R\). Hence, a partition of \(G^h\) contributes has state \(s'\) and weight \(\omega\) if and only if the same partition has state \(s'_{\rightarrow \gamma^R}\) and weight \(\omega\) in \(\hat{G}\).

Therefore, for every state \(s\in\states\), it holds that \[\hat{A}^{\omega}[s] = \orstack{s'\in\states^{2k}\\ (s')_{\rightarrow \gamma^R}=s\downop} A_h^{\omega}[s'].\] This is exactly the same invariant as in the definition of the algorithmic table \(\hat{T}_0^{\omega}\). Since we already proved that \(A_h^{\omega}=T_h^{\omega}\) for every \(\omega\in [n]_0\), it follows that \(\hat{A}^{\omega}=\hat{T}_0^{\omega}\) for every \(\omega\in [n]_0\).

Finally, we show that \(A_x^{\omega}=T_x^{\omega}\). Since \(G_x\) results from the graph \(\hat{G}\) by applying the relabeling \(\beta\), it holds for each \(s\in \states\) that \[A_x^{\omega}[s] = \orstack{s'\in\states\\ (s')_{\rightarrow \beta}=s} \hat{A}^{\omega}[s'].\] Since this is exactly the definition of \(T_x^{\omega}\) from \(\hat{T}_0^{\omega}\), and since we already proved that \(\hat{A}_0^{\omega}=\hat{T}_0^{\omega}\), it follows that \(A_x^{\omega}=T_x^{\omega}\). ◻

Proof. Let \(N \coloneq |\states^{2k}|\). Since \(\mathcal{M}^{2k}_d\) contains all multisets of size at most \(d-1\) over \([2k]\), it holds that \[|\mathcal{M}^{2k}_d| \leq \sum_{j=0}^{d-1} (2k)^j = \frac{(2k)^d-1}{2k-1} \leq \frac{2^d k^d}{2k - k} = \Oh(k^{d-1}).\] It follows that \(N = (n+1)^{|\mathcal{M}^{2k}_d|} = n^{\Oh(k^{d-1})}\). Since \(\states \subseteq \states^{2k}\), we also have \(|\states| \leq N\).

Now we show for every node \(x\in\nodes\), that all tables \(T_x^{\omega}\) for all values of \(\omega\) can be computed in polynomial time in \(N\) assuming that the tables \(T_{x'}^{\omega'}\) for all children \(x'\) of \(x\) and all values \(\omega'\) are given. Since we assume that the size of \(\syntaxtree\) is bounded polynomially in \(n\), this implies that the whole algorithm runs in polynomial time in \(N\) following a bottom up dynamic programming scheme, and thus in time \(n^{\Oh(k^{d-1})}\), which proves the claim.

The bound is trivial for an introduce node \(x\), since we can set the values \(T_x^{\omega}\) directly by iterating over all values of \(\omega\) and all entries \(s\in \states\).

Consider now a join node \(x\). The number of values of \(\omega\) is \(n+1\), and the number of pairs \((X_i,Y_i)\) we iterate over is bounded by \(h = N^2\). The table \(T_0^{\omega}\) is computed by considering pairs of states \(s_1,s_2\in \states\). Thus, for each fixed value of \(\omega\), this requires at most \(|\states|^2\leq N^2\) combinations, and therefore all tables \(T_0^{\omega}\) are computed in time polynomial in \(N\).

Now some value \(i\in [h]\), and assume that we have computed the tables \(T_{i-1}^{\omega'}\) for all \(\omega'\in [n]_0\). If \((X_i,Y_i)\) is not feasible, then \(T_i=T_{i-1}\). Otherwise, for each value \(\omega\in [n]_0\) and each state \(s\in \states^{2k}\), the algorithm iterates over all \(r'\in [\min\{s(X_i), s(Y_i)\}]_0\). Since \(s(X)\) is bounded by \(n\) for each state \(s\) and a set \(X\), there are at most \(n+1\) choices for \(r'\). For each such choice, the resulting state \(s'\) is obtained by modifying a constant number of coordinates of \(s\). Hence one transition from \(T_{i-1}\) to \(T_i\) requires polynomial time in \(N\). Since there are \(h\) such transitions, all auxiliary tables \(T_i^{\omega}\) are computed in time polynomial in \(N\).

Finally, the table \(T_x^{\omega}\) is obtained from \(T_h^{\omega}\) by first computing \(\hat{T}^{\omega}\) via the relabeling \(\gamma^R\), then restricting it to \(\hat{T}_0^{\omega}\) on \(\states\), and then applying the relabeling \(\beta\). Each of these three steps takes at most polynomial time in \(N\), by iterating over all relevant states and updating the corresponding entry of the next table. Hence \(T_x^{\omega}\) can be computed from \(T_h^{\omega}\) in polynomial time in \(N\). This concludes the proof. ◻

Proof of  1. Given the instance \((G,\target)\), together with a \(k\)-clique-expression of \(G\) for some positive integer \(k\), we first compute a \(k\)-NLC-expression of \(G\). As discussed in the preliminaries, this can be done in polynomial time. Let \(\syntaxtree\) be the syntax tree of the computed NLC-expression, and let \(\nodes\) be the set of nodes of \(\syntaxtree\). Our algorithm then computes all tables \(T_x^{\omega}\) for each node \(x\in \nodes\) and each value \(\omega \in [n]_0\) using 1. It outputs YES, if there exists some mapping \(s\in \states\) with \(T_r^{\target}[s]=1\), where \(r\) is the root of \(\syntaxtree\), and NO otherwise. The correctness of the algorithm follows from 1. The algorithm runs in time \(n^{\Oh(k^{d-1})}\) by 2. ◻

Proof. We show first that there exists a fixed integer \(k_0\) (that depends on \(d\) only), such that for each integer \(k\geq k_0\) there exists an integer \(k'\) with \(k\leq \binom{k'}{d} < 2k\). We choose \(k_0\) to be the smallest integer such that for the smallest integer \(k'_0\) with \(\binom{k'_0}{d}\geq k\) it holds that \(k'_0 \geq 2d\). Then it holds for each \(k\geq k_0\) and for \(k'\) the smallest integer with \(\binom{k'}{d}\geq k\) that \(k'\geq k'_0\geq 2d\), and thus \[\begin{align} &\frac{\binom{k'}{d}}{k}\leq\frac{\binom{k'}{d}}{\binom{k'-1}{d-1}}\\ &= \frac{k'!}{d!(k'-d)!}\frac{(d-1)!(k'-1-d)!}{(k'-1)!}\\ &= \frac{k'}{k'-d} = \frac{k'-d+d}{k'-d} = 1 + \frac{d}{k'-d} \leq 2. \end{align}\]

Now we prove the claim. Assume that there exists an algorithm that solves the \(d\)-Binomial Multi-Colored Clique problem in time \(n^{o\big(\binom{k'}{d}\big)}\) on graphs with \(\binom{k'}{d}\) partitions, where each color class has the same number of vertices and the same number of edges between each pair of color classes.

Given an arbitrary instance of the Multi-Colored Clique problem with \(k\) colors, such that each color class has \(n\) vertices and there are \(m\) edges between each pair of color classes, for some integers \(n,m,k \in \mathbb{N}\), we construct the instance of the \(d\)-Binomial Multi-Colored Clique problem as follows: If \(k = \binom{k'}{d}\) for some integer \(k'\), then we use the same instance as the input. Otherwise, we create an instance with \(\binom{k'}{d}\) color classes where \(k'\) is the smallest integer with \(\binom{k'}{d}\geq k\), by adding \(\binom{k'}{d}-k\) new partitions to the input graph, each containing \(2n\) vertices. We also add \(n\) vertices to each of the original \(k\) partitions. We make each of the first \(n\) vertices of the added partitions adjacent to the original \(n\) vertices of each of the original \(k\) partitions, and to the first \(n\) vertices of each of the other added partitions. Finally, for any pair of original partitions, we add arbitrary edges between the vertices added to these partitions to increase the number of edges between them to \(n^2\). This results in an instance with \(\binom{k'}{d}\) partitions, where each partition has \(2n\) vertices, and there are \(n^2\) edges between each pair of partitions.

We claim that the resulting instance admits a clique with a vertex from each partition if and only if the original instance admits one. Clearly, such a clique must contain a vertex from the first \(n\) vertices of each added partition, since the other \(n\) vertices are isolated. Since there exist at least one added partition, and since each such vertex is adjacent to all and only to the original \(n\) vertices of each original partition, such a clique must contain a vertex from each of the original \(k\) partitions, and thus it is a multi-colored clique in the original instance. Conversely, each such clique can be extended to a clique in the final graph by including the first vertex of each added partition.

Hence, by applying the assumed algorithm for the \(d\)-Binomial Multi-Colored Clique problem on the constructed instance, we can solve the original instance of the Multi-Colored Clique problem in time \((2n)^{o\big(\binom{k'}{d}\big)}\) = \(n^{o\big(k\big)}\) since we can assume that \(\binom(k') {d} < 2k\). This contradicts 3, and thus the claim follows.

Finally, the \(W[1]\)-hardness of the \(d\)-Binomial Multi-Colored Clique problem follows from the fact that the Multi-Colored Clique problem is \(W[1]\)-hard parameterized by \(k\), and that the reduction described above is a parameterized reduction. ◻

Proof. Let \(Q\) be a multi-colored clique in \(H\). For each color \(C\in R\), let \(u_C^{i_C}\in V_C\) be the unique vertex of \(Q\) in the color class \(V_C\), where \(i_C\in [n]\) is its id. We show how to partition \(V(G)\) into cliques of size exactly \(d\).

We start with the color gadgets. Fix a color \(C\in R\), and consider an id gadget \(\idgad_C^q\) whose inner cut is present. Let \(L_C^q\) and \(R_C^q\) be its left and right color columns. Each of these columns consists of \(n\) vertex-disjoint \((d-1)\)-cliques; we denote them by \(L_C^q(1),\dots,L_C^q(n)\) and \(R_C^q(1),\dots,R_C^q(n)\). Let \(I_C^q=\{x_1,\dots,x_n\}\) be the inner cut of \(\idgad_C^q\). For each \(t\in [n]\), we pack \(x_t\) together with \(L_C^q(t)\) in a \(d\)-clique if it holds that \(t\leq i_C\), and with \(R_C^q(t)\) otherwise. Since every vertex of the inner cut is adjacent to all vertices of both neighboring columns, this yields \(n\) cliques of size \(d\). Hence exactly the first \(i_C\) vertices of the inner cut are packed with the left column, and the remaining \(n-i_C\) vertices are packed with the right column.

Now let \(O\) be an outer cut of the same color gadget, lying between two consecutive id gadgets. We pack \(O\) in the reverse way: for \(O=\{x_1,\dots,x_n\}\) and its neighboring columns are \(L\) on the left and \(R\) on the right (for the outer cut added the end of each color gadget, we consider the last color column as its left, and the very first one as its right), then for each \(t\in [n]\) we put \(y_t\) together with \(L(t)\) if \(t> i_C\), and with \(R(t)\) otherwise. Thus an outer cut sends the first \(i_C\) vertices to the right and the remaining vertices to the left. Applying this rule to every outer cut shows that the same value \(i_C\) is propagated through the whole color gadget. In particular, every \((d-1)\)-clique in a color column that does not belong to an edge gadget is extended by exactly one cut vertex to a \(d\)-clique.

Next consider a pair of colors \(L_q=\{C_1,C_2\}\in \mathscr{L}\) and the corresponding edge gadget. Since \(Q\) is a clique in \(H\), the selected vertices \(u_{C_1}^{i_{C_1}}\) and \(u_{C_2}^{i_{C_2}}\) are adjacent in \(H\). Let \(\simpegad_q\) be the simple edge gadget corresponding to that edge, and Let \(v_1,\dots,v_n\),\(w_1,\dots,w_n\) be the vertices of \(\simpegad_q\), where the vertices \(v_t\) are adjacent to the id gadget of \(C_1\) and the vertices \(w_t\) are adjacent to the id gadget of \(C_2\). We use this simple edge gadget instead of the deleted inner cuts. For each \(t\in [n]\), we pack \(v_t\) together with the \(t\)-th \((d-1)\)-clique of the first column of \(\idgad_{C_1}^q\) if \(t\leq i_{C_1}\), and with the \(t\)-th \((d-1)\)-clique of the second column otherwise. Analogously, we pack \(w_t\) together with the \(t\)-th \((d-1)\)-clique of the first column of \(\idgad_{C_2}^q\) if \(t\leq i_{C_2}\), and with the \(t\)-th \((d-1)\)-clique of the second column otherwise. These adjacencies exist by the definition of a simple edge gadget. Therefore the chosen simple edge gadget realizes exactly the same left-right split as the deleted inner cuts of both id gadgets.

It remains to cover the vertices inside the selection gadgets. Consider the selection gadget attached to the family \(\mathcal{F}=\{X_1,\dots,X_m\}\) of simple edge gadgets for the pair \(L_q\), and let \(X_p=V(\simpegad_q)\) be the set corresponding to the chosen edge. We first construct a triangle packing between \(\mathcal{F}\setminus\{X_p\}\) and the selection columns. For each \(j<p\), we use the selection column between \(X_j\) and \(X_{j+1}\) to cover \(X_j\), and for each \(j\geq p\), we use the selection column between \(X_j\) and \(X_{j+1}\) to cover \(X_{j+1}\).

Fix one such column \(C_j\). In the former case (\(j<p\)), let \(X_j = v_1,\dots,v_r\). By construction of the selection column, every odd-indexed vertex \(v_t\) is adjacent to all vertices of the color classes \(c_1\) and \(c_2\), while every even-indexed vertex \(v_t\) is adjacent to all vertices of the color classes \(c_3\) and \(c_0\). Hence, for each \(t\in[r]\), we can build a triangle between \(v_t\) and the endpoints of the \((2t-1)\)st edge of the cycle (as the endpoints of such edges alternate in colors between \(1,2\) and \(3,0\)). Similarly, for the latter case (\(j\geq p\)), let \(X_{j+1} = v_1, \dots, v_r\). Then every odd-indexed vertex \(v_t\) is adjacent to all vertices of the color classes \(c_2\) and \(c_3\), while every even-indexed vertex \(v_t\) is adjacent to all vertices of the color classes \(c_1\) and \(c_0\). Hence, for each \(t\in[r]\), we can build a triangle between \(v_t\) and the endpoints of the \((2t)\)th edge of the cycle (as the endpoints of such edges alternate in colors between \(2,3\) and \(0,1\)). In both cases, we obtain \(r\) vertex-disjoint triangles that cover exactly the vertices of the chosen set together with all vertices of \(C_j\). Doing this for every selection column yields a triangle packing that covers all vertices of the selection gadget and all vertices in \(\mathcal{F}\setminus\{X_p\}\), while leaving the vertices of \(X_p\) uncovered inside the selection gadget.

Finally, for each triangle in this packing, we choose one of the attached cliques of size \(d-3\) and add all its vertices to the triangle. Since every such clique is adjacent to all vertices of the corresponding selection column and all vertices of the sets in \(\mathcal{F}\), each triangle extends to a clique of size \(d\). As the attached \((d-3)\)-cliques are pairwise disjoint and their number is exactly \(r\) per selection column, this turns the triangle packing above into a \(d\)-clique partition of the whole selection gadget together with all sets \(X_j\) for \(j\neq p\).

We perform the above construction independently for every color gadget, and for every edge gadget corresponding to every pair of colors. It is not hard to see that both inner cuts and simple edge gadgets consume the same number of \((d-1)\)-cliques from the left color column of each id gadget, and the same number of \((d-1)\)-cliques from the right color column, where the outer cuts complement these selections by consuming the remaining \((d-1)\)-cliques. It also holds that every non-chosen simple edge gadget is absorbed by its selection gadget. Consequently, every vertex of \(G\) belongs to exactly one clique of size \(d\). Hence \(G\) has a \(d\)-clique partitioning. ◻

Proof. Fix an arbitrary selection column \(C_j\) for \(j\in[m-1]\). First note that no clique of \(\mathcal{P}\) can contain a single vertex of \(C_j\), since each vertex of \(C_j\) is only adjacent to the \((d-3)\)-cliques, to two other vertices of \(C_j\), and to the vertices of \(X_j\) and \(X_{j+1}\) that are pairwise non-adjacent—as they induce an independent set by definition. On the other hand, since \(C_j\) induces a simple cycle in \(G\), each clique of \(\mathcal{P}\) contains at most two vertices of \(C_j\) that appear consecutively on the cycle. Therefore, the intersection of \(E(\mathcal{P})\) with \(C_j\) must be one of the two perfect matchings of \(C_j\), either the “horizontal” one or the “vertical” one.

By construction of the gadget, vertices of \(X_j\) are only adjacent to endpoints of the edges of the horizontal matching, while vertices of \(X_{j+1}\) are only adjacent to endpoints of the edges of the vertical matching. Therefore: If \(\mathcal{P}\) packs the edges of the horizontal matching, then all cliques covering \(C_j\) use vertices of \(X_j\) (and none of \(X_{j+1}\)), and if \(\mathcal{P}\) packs the edges of the vertical matching, then all cliques covering \(C_j\) use vertices of \(X_{j+1}\) (and none of \(X_j\)). Hence, exactly \(r\) vertices are taken from exactly one of the two adjacent sets consuming all vertices of \(C_j\) and all vertices of the selected set, while no vertex of the other set is used.

Therefore, there must exist a unique index \(i\in [m]\) such that for all \(j<i\), the columns \(C_j\) cover all vertices of \(X_j\) and for all \(i\leq j \leq m-1\), the columns \(C_j\) cover all vertices of \(X_{j+1}\). Hence, all vertices of \(X_i\) are not covered by any column, and thus must be covered by cliques that only intersect the selection gadget in \(X_i\) itself. ◻

Proof. We prove the claim for two consecutive id gadgets of the same color gadget. The proof of the lemma then follows follows by induction. Let \(\idgad^q\) and \(\idgad^{q+1}\) be consecutive id gadgets in one fixed color gadget, and let \(O^q\) be the outer cut between them. Let \(s \coloneq s(\idgad^q)\). By definition of the state, exactly \(s\) \((d-1)\)-cliques of the left color column of \(\idgad^q\) are completed together with the inner cut or with the replacing edge gadget. Hence exactly \(n-s\) \((d-1)\)-cliques of the right color column of \(\idgad^q\) are completed with that inner cut or edge gadget respectively, and therefore the remaining \(s\) \((d-1)\)-cliques of that right column must be completed with vertices of the outer cut \(O^q\).

The set \(O^q\) is an independent set of size \(n\), and each vertex of \(O^q\) is adjacent to all vertices of the right color columns of \(\idgad^q\) and the left color columns of \(\idgad^{q+1}\). Thus every clique of \(\mathcal{P}\) containing a vertex of \(O^q\) contains exactly one vertex of \(O^q\) and one \((d-1)\)-clique from one of its two neighboring columns. Therefore, exactly \(n-s\) vertices of \(O^q\) are with \((d-1)\)-cliques of the left column of \(\idgad^{q+1}\).

Consequently, exactly \(n-s\) \((d-1)\)-cliques of the left color column of \(\idgad^{q+1}\) are consumed by \(O^q\). The remaining \(s\) \((d-1)\)-cliques of that left column must be completed with the inner cut of \(\idgad^{q+1}\) or with its replacing edge gadget. By definition of the state of an id gadget, it follows that \(s(\idgad^{q+1}) = s\), which proves the claim. ◻

Proof. Let \(i_1 \coloneq s(\idgad_{C_1}^q)\) and \(i_2 \coloneq s(\idgad_{C_2}^q)\). We show that \(\{u_{C_1}^{i_1},u_{C_2}^{i_2}\}\in E(H)\).

Let \(\mathcal{F}=\{X_1,\dots,X_m\}\) be the family of vertex sets of the simple edge gadgets contained in the edge gadget between \(\idgad_{C_1}^q\) and \(\idgad_{C_2}^q\). By the previous lemma on selection gadgets, there exists a unique index \(p\in [m]\) such that all vertices of \(X_j\) for \(j\neq p\) are covered by cliques lying completely inside the selection gadget, while the vertices of \(X_p\) belong to cliques that intersect the selection gadget only in \(X_p\). Hence the only simple edge gadget that can interact with the two id gadgets is the gadget corresponding to \(X_p\).

Let \(X_p=V(\simpegad_p)\), and let \(\{u_{C_1}^{j_1},u_{C_2}^{j_2}\}\) be the edge of \(H\) represented by \(\simpegad_p\). By construction of the simple edge gadget, its vertices are partitioned into vertices \(v_1,\dots,v_n\) adjacent to \(\idgad_{C_1}^q\) and vertices \(w_1,\dots,w_n\) adjacent to \(\idgad_{C_2}^q\), where \(v_1,\dots,v_{j_1}\) are adjacent to all vertices of the first color column of \(\idgad_{C_1}^q\) and \(v_{j_1+1},\dots,v_n\) are adjacent to all vertices of the second color column, and analogously \(w_1,\dots,w_{j_2}\) are adjacent to the first color column of \(\idgad_{C_2}^q\) while \(w_{j_2+1},\dots,w_n\) are adjacent to its second color column.

Since the vertices of \(X_p\) are not covered inside the selection gadget, every vertex \(v_t\) must be packed with one of the two color columns of \(\idgad_{C_1}^q\), and every vertex \(w_t\) must be packed with one of the two color columns of \(\idgad_{C_2}^q\). Therefore exactly \(j_1\) \((d-1)\)-cliques of the left column of \(\idgad_{C_1}^q\) are completed using vertices of \(X_p\), and the remaining \(n-j_1\) such cliques are completed on the right side. By the definition of the state of an id gadget, this means that \(s(\idgad_{C_1}^q)=j_1\). The same argument on the \(C_2\)-side yields \(s(\idgad_{C_2}^q)=j_2\).

Consequently, \(\Big\{u_{C_1}^{s(\idgad_{C_1}^q)},u_{C_2}^{s(\idgad_{C_2}^q)}\Big\}=\big\{u_{C_1}^{j_1},u_{C_2}^{j_2}\big\}\) is exactly the edge of \(H\) corresponding to the simple edge gadget \(\simpegad_p\), and hence, the two states correspond to an edge of \(H\). ◻

Proof. We construct a multi-colored clique in \(H\) from \(\mathcal{P}\). For each color \(C\in R\), consider the color gadget \(\colgad_C\). By 6, all id gadgets contained in \(\colgad_C\) have the same state. We denote this common value by \(s_C\). We now select in the color class \(V_C\) the vertex \(u_C^{s_C}\). Let \(S \coloneq \{u_C^{s_C} \mid C\in R\}\). We claim that that \(S\) is a clique in \(H\).

Let \(C_1,C_2\in R\) be two distinct colors, and consider the index \(q\in[\ell]\) such that \(L_q=\{C_1,C_2\}\). Since the two id gadgets \(\idgad_{C_1}^q\) and \(\idgad_{C_2}^q\) linked by the corresponding edge gadget, it follows then from 7 that \(\Big\{u_{C_1}^{s(\idgad_{C_1}^q)}, u_{C_2}^{s(\idgad_{C_2}^q)}\Big\}\in E(H)\). Since \(C_1\) and \(C_2\) were chosen arbitrarily, it follows that \(S\) is a clique in \(H\). ◻

Proof. Since \(\hat{G}\) is a supergraph of \(G\) with the same set of vertices, if \(G\) has a \(d\)-clique partitioning, then \(\hat{G}\) also has one. For the other direction, we show that \(G\) and \(\hat{G}\) have the same set of \(d\)-cliques. Let \(C\) be a \(d\)-clique in \(\hat{G}\). If \(C\) does not intersect a color column, then \(C\) is clearly a \(d\)-clique in \(G\) as well.

Otherwise, we claim that \(C\) consists of \(d-1\) vertices of color columns and a single vertex that does not belong to a color column. This holds since the vertices of color columns are partitioned into \((d-1)\)-cliques without edges between them, and any two vertices that do not belong to color columns and adjacent to color column vertices are not adjacent themselves. So the only case a \(d\)-clique of \(\hat{G}\) doesn’t belong to \(G\) is if it contains a vertex \(w\) of an inner cut, out cut or simple edge gadget attached to a color column \(Q_C^q(X)\) together with \((d-1)\)-clique of a different color column in the same grid column \(\idgad_{C'}^q\) with \(C\neq C'\). However, since \(|C|=|C'|=d\), and \(C\neq C'\), \(C'\) must contain a color that does not belong to \(C\), and hence, the vertex \(w\) is not adjacent to all vertices of that \((d-1)\)-clique, contradicting the assumption that \(C\) is a clique. Therefore, every \(d\)-clique of \(\hat{G}\) is a \(d\)-clique of \(G\), and thus if \(\hat{G}\) has a \(d\)-clique partitioning, then \(G\) also has one. ◻

Proof. Since the syntax tree of a linear clique-expression has a caterpillar structure, where all inner nodes are union nodes with a single introduce child, we consider a linear clique expression as a sequence of operations, each adding a vertex of a specific label to the graph, relabeling some label, or adding edges between labels. We will consider each operation of this sequence a “timestamp”, and denote the graph constructed after the first \(t\) operations by \(\hat{G}_t\).

We will preserve labels that will be used ot specific purposes. We first preserve the first \(2k\) labels, where the first \(k\) labels \(\ell_1, \dots, \ell_k\) are used to construct the left color columns of the id gadgets, and the following \(k\) labels \(r_1, \dots, r_k\). are used to construct the right color columns of the id gadgets. We preserve the following \(k\) labels \(\ell^0_1, \dots, \ell^0_k\) for the very first color column of each color gadget. We also preserve \(d-1\) labels \(c_1, \dots c_{d-1}\) for creating the cliques of these color columns.

We preserve \(8\) labels \(z_0, \dots, z_3, z'_0, \dots, z'_3\) and three extra labels \(y_0\), \(y\) and \(y'\) for creating the selection columns of the selection gadgets, and the labels \(e\) and \(e'\) for the \((d-3)\)-cliques attached to them. We preserve the labels \(s\) and \(s'\) for creating independent sets and cliques. We also preserve a “forget” label \(f\). Vertices of label \(f\) at a timestamp \(t\) already have all their neighbors in \(\hat{G}\) adjacent to them in \(\hat{G}_t\).

When we say we add an independent set or a clique of size \(r\), we mean that we add \(r\) vertices of label \(s\), where in the case of a clique, we add each vertex with label \(s'\), we join it with label \(s\) and then relabel it to the label \(s\). When we use this operation, we assume that no other vertex has label \(s\) at that timestamp. After applying this operation, we will join the created independent set or clique with some other labels of \(G_t\), and then relabel all its vertices, freeing both labels \(t\) and \(t'\). Similarly, when we say we create a \((d-1)\)-clique of an id gadget \(\idgad_{C}^q\), we mean that we add \(d-1\) vertices of labels \(c_1,\dots c_{d-1}\), we add all edges between all these labels, and then injectively relabel these labels to the labels \(\{\ell^0_c\colon c\in C\}\) if this is the first color column of the color gadget of color \(C\), to \(\{\ell_c\colon c\in C\}\) if this is a left color column of an id gadget of color \(C\), or to \(\{r_c\colon c\in C\}\) if this is a right color column of an id gadget of color \(C\).

Now we describe the construction of \(G\) step by step. The construction will be divided into phases, where in each phase we create a grid column. We preserve the following two invariants:

The latter invariant ensures that we can add edges between the grid columns and the inner cuts, outer cuts and simple edge gadgets attached to them by a single join operation per gadget, without affecting the other grid columns, where the other grid columns either are already forgotten, or not constructed yet.

Now we describe each phase. The phase starts by constructing the left color columns of the \(q\)-th id gadgets of each color gadget, by creating \((d-1)\)-cliques one by one. After that, if this is not the first phase, we create the outer cut between the \(q\)-th and the \((q-1)\)-th id gadgets of each color gadget corresponding to a color \(C\), by adding an independent set of size \(n\) and joining it with all labels \(\ell_c\) and \(r_c\) for \(c \in C\). After that we forget all label \(r_c\) for all \(c\in[k]\), and then we create the right color columns of the \(q\)-th id gadgets of each color gadget, by creating \((d-1)\)-cliques one by one.

Finally, we create the edge gadget corresponding to \(L_q\), as follows: we will create the simple edge gadgets one by one. For each we will ensure that the selection columns preceding and following it (if exist) are already created, where a vertex of the selection column preceding with color \(i\) it will be assigned the label \(z_i\), and a vertex of the selection column following it with color \(i\) will be assigned the label \(z'_i\). Remember that the color assigned to a vertex of a selection column is defined by its id on the cycle modulo \(4\).

The process begins by relabeling \(z'_i\) to \(z_i\) for all \(i\in[4]\) and \(e'\) to \(e\), since if this was not the first selection gadget, then the selection column preceding the current simple edge gadget is the selection column following the previous simple edge gadget. After that we create the selection column following the current simple edge gadget, if exists, by creating the \((d-3)\)-cliques and a cycle on \(2r\) vertices and assigning labels \(z'_0,\dots z'_3\) as follows: in each step we add a vertex of label \(y'\), make it adjacent to label \(y\), relabel \(y\) to \(z'_i\) (except for the very first vertex, we relabel it to \(y_0\)) for the appropriate \(i\), and then we relabel \(y'\) to \(y\). Finally, for the last vertex, we join it to \(y_0\) and relabel both \(y_0\) and \(y\) to \(z'_1\) and \(z'_0\) respectively. After that we create the \(r\) \((d-1)\)-cliques using the labels \(s'\) and \(s\), relabeling each to \(e'\) after creating. After that we make these cliques adjacent to all vertices of the selection column by joining \(e\) with \(z'_i\) for all \(i\in[4]\).

Then we create the simple edge gadget consisting of four independent sets one by one, the definition of a simple id gadget, where for each we create an independent set of the appropriate size, we make it adjacent to all corresponding colors of the corresponding grid columns, selection columns preceding and following it and the \((d-3)\)-cliques attached to them, and then we forget its labels (the vertices of this independent set must have label \(s\) at this point). After we create a simple edge gadget we forget the labels of the preceding selection column and its \((d-3)\)-cliques.

Finally, after creating the last grid column, we create the outer cuts between the last id gadgets and the first id gadgets of each color gadget, by creating an independent set of size \(n\) and joining it with all labels \(\ell^0_c\) for \(c\in C\) for each color \(C\). This concludes the construction of \(\hat{G}\).

It is not hard to see that the resulting graph is exactly the graph \(\hat{G}\). In particular, all colored vertices are assigned edges defined by their colors, and not by their ids, and therefore, assigning the labels accordingly yields the correct adjacencies. Since we only use \(\Oh(k)\) labels, the width of the constructed linear clique expression is \(\Oh(k)\). Clearly, such a linear clique expression can be constructed in polynomial time given the instance \(H\). ◻

Proof of 2. The \(W[1]\)-hardness follows from 2, since the reduction presented above fulfills all the requirements of a parameterized reduction. For the latter part, assume that there exists an algorithm solving \(d\)-in time \(n^{o(k^{d-1})}\) on graphs of linear clique-width \(k\) when given together with a linear \(k\)-clique expressions. We show that this would contradict ETH by providing an algorithm solving \((d-1)\)-Binomial Multi-Colored Clique in time \(n^{o\big(\binom{k}{d}\big)}\).

Given an instance \(H\) of \((d-1)\)-Binomial Multi-Colored Clique, we construct the graph \(\hat{G}\) together with a linear \(k\)-clique-expression of \(\hat{G}\) of width \(\Oh(k)\) as described above. By 10 this can be done in polynomial time. It holds by 4 and 8 that \(H\) has a multi-colored clique if and only if \(\hat{G}\) has a \(d\)-clique partitioning. Hence, we can solve the instance \(H\) by running the assumed algorithm on the instance \(\hat{G}\). Since the size of \(\hat{G}\) is bounded polynomially, this algorithm solves the instance \(H\) in time \(n^{o(k^{d-1})}\), contradicting ETH. ◻