# On Finding and Enumerating Maximal and Maximum \(k\)-Partite Cliques in \(k\)-Partite Graphs
## 4 Complexity-Theoretic Issues
To these we add 12 edges: (\(x_{i,1}\), \(y_{i,1}\)), (\(x_{i,2}\), \(y_{i,2}\)), (\(x_{i,3}\), \(y_{i,3}\)), (\(x_{i,1}\), \(z_{i,2}\)), (\(x_{i,1}\), \(z_{i,3}\)), (\(x_{i,2}\), \(z_{i,1}\)), (\(x_{i,2}\), \(z_{i,3}\)), (\(x_{i,3}\), \(z_{i,1}\)), (\(x_{i,3}\), \(z_{i,2}\)),(\(y_{i,1}\), \(z_{i,1}\)), (\(y_{i,2}\), \(z_{i,2}\)), (\(y_{i,3}\), \(z_{i,3}\)). The resulting subgraph is illustrated in Figure 3. Next, we use literals to place edges between subgraphs. Whenever \(C_{i}\) and \(C_{j}\), \(i\
eq j\), contain the same literal \(l_{i,s}=l_{j,t}\), we add six more edges: two of the form (\(x_{i,s}\), \(z_{j,h}\)), where \(h\
eq t\); two of the form (\(x_{j,t}\), \(z_{i,h}\)), where \(h\
eq s\); and two of the form (\(y_{i,s}\), \(z_{j,t}\)) and (\(y_{j,t}\), \(z_{i,s}\)). This construction is depicted in Figure 4, using \(l_{i,2}=l_{j,3}\) as an example. Should \(C_{i}\) and \(C_{j}\), \(i\
eq j\), contain two matching literals, then 12 edges are added. For an example of this see Figure 5, where \(l_{i,1}=l_{j,2}\) and \(l_{i,2}=l_{j,3}\). Two clauses cannot of course contain three identical literals and remain distinct. Observe that this transformation creates three independent sets in \(G\), namely, those vertices labeled by \(x\), those labeled by \(y\), and those labeled by \(z\). Thus, \(G\) is a balanced 3-partite graph with \(9m\) vertices and \(12m+6d\) edges, where \(d\) is the number of matching literal pairs. The reduction takes at most \(O(m^{2})\) time, realized by comparing each pair of clauses for identical literals. We now show that \(E\) is satisfiable if \(G\) possesses an independent set \(I\) of size \(4m\), with each partite set of \(G\) containing at least one element of \(I\). We first prove the forward (only if) implication. Suppose \(E\) is one-in-three satisfiable, and let \(A\) denote a satisfying truth assignment for \(E\). Then consider a candidate for \(I\) defined by the following rule, where \(1\leq i\leq m\): should \(l_{i,1}\) be true under \(A\), then \(I\) contains \(x_{i,1}\), \(y_{i,2}\), \(y_{i,3}\) and \(z_{i,1}\); should \(l_{i,2}\) be true under \(A\), then \(I\) contains \(x_{i,2}\), \(y_{i,1}\), \(y_{i,3}\), and \(z_{i,2}\); and should \(l_{i,3}\) be true under \(A\), then \(I\) contains \(x_{i,3}\), \(y_{i,1}\), \(y_{i,2}\), \(z_{i,3}\). \(I\) is clearly of size \(4m\), and each partite set of \(G\) contains at least one (in fact at least \(m\)) elements from \(I\). Figure 3: Subgraph produced from the \(i\)th clause of a one-in-three SAT instance. It remains only to show that \(I\) is an independent set. The four vertices that correspond to any single clause are plainly independent. The eight vertices that correspond to a pair of clauses are independent as well, as long as the literals in these clauses are distinct. If a pair of clauses contain any matching literals, however, then there are two possibilities to consider: either the clauses contain just one matching literal or they contain two. Suppose \(C_{i}\) and \(C_{j}\), \(i\
eq j\), share exactly one matching literal. Without loss of generality, assume the configuration is as depicted in Figure 4, where \(l_{i,2}=l_{j,3}\). Should \(l_{i,2}\) (and hence \(l_{j,3}\)) be true under \(A\), then the aforementioned rule identifies \(x_{i,2}\), \(y_{i,1}\), \(y_{i,3}\), \(z_{i,2}\), \(x_{j,3}\), \(y_{j,1}\), \(y_{j,2}\), and \(z_{j,3}\) as the members of \(I\), and indeed these eight vertices are independent.