# On Finding and Enumerating Maximal and Maximum \(k\)-Partite Cliques in \(k\)-Partite Graphs
## 4 Complexity-Theoretic Issues
Should \(l_{i,2}\) (and hence \(l_{j,3}\)) be false under \(A\), then one of the following four events must occur, and again the aforementioned rule applies: \(l_{i,1}\) and \(l_{j,1}\) are true under \(A\), and so \(x_{i,1}\), \(y_{i,2}\), \(y_{i,3}\), \(z_{i,1}\), \(x_{j,1}\), \(y_{j,2}\), \(y_{j,3}\), and \(z_{j,1}\) are members of \(I\); \(l_{i,1}\) and \(l_{j,2}\) are true under \(A\), and so \(x_{i,1}\), \(y_{i,2}\), \(y_{i,3}\), \(z_{i,1}\), \(x_{j,2}\), \(y_{j,1}\), \(y_{j,3}\), and \(z_{j,2}\) are members of \(I\); \(l_{i,3}\) and \(l_{j,1}\) are true under \(A\), and so \(x_{i,3}\), \(y_{i,1}\), \(y_{i,2}\), \(z_{i,3}\), \(x_{j,1}\), \(y_{j,2}\), \(y_{j,3}\), and \(z_{j,1}\) are members of \(I\); or \(l_{i,3}\) and \(l_{j,2}\) are true under \(A\), and so \(x_{i,3}\), \(y_{i,1}\), \(y_{i,2}\), \(z_{i,3}\), \(x_{j,2}\), \(y_{j,1}\), \(y_{j,3}\), and \(z_{j,2}\) are members of \(I\). In each event, \(I\) contains eight independent vertices. Now suppose \(C_{i}\) and \(C_{j}\), \(i\
eq j\), share two matching literals. Without loss of generality, assume the configuration is as depicted in Figure 5, where \(l_{i,1}=l_{j,2}\) and \(l_{i,2}=l_{j,3}\). Should \(l_{i,1}\) (and hence \(l_{j,2}\)) be true under \(A\), then the aforementioned rule identifies \(x_{i,1}\), \(y_{i,2}\), \(y_{i,3}\), \(z_{i,1}\), \(x_{j,2}\), \(y_{j,1}\), \(y_{j,3}\), and \(z_{j,2}\) as the members of \(I\), and indeed these eight vertices are independent. Should \(l_{i,1}\) (and hence \(l_{j,2}\)) be false under \(A\), then one of the following two events must occur, and again the aforementioned rule applies: \(l_{i,2}\) (and hence \(l_{j,3}\)) are true under \(A\), and so \(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}\) are members of \(I\); or \(l_{i,3}\) (and hence, because both pairs of identical literals are false, \(l_{j,1}\)) are true under \(A\), and so \(x_{i,3}\), \(y_{i,1}\), \(y_{i,2}\), \(z_{i,3}\), \(x_{j,1}\), \(y_{j,2}\), \(y_{j,3}\), and \(z_{j,1}\) are members of \(I\). Again, in each event, \(I\) contains eight independent vertices. We conclude that no matter how pairs of clauses may share matching literals, \(I\) remains an independent set. We now prove the reverse (if) implication. Suppose \(G\) has an independent set \(I\) of size \(4m\), with the property that each particle set of \(G\) contains at least one element from \(I\). Then consider a candidate truth assignment \(A\) defined by the following rule, where \(1\leq i\leq m\) and \(1\leq j\leq 3\): literal \(l_{i,j}\) is set to true iff \(x_{i,j}\) is in \(I\). Our task is to show that \(E\) is one-in-three satisfied by \(A\). Figure 4: Subgraph connections where \(l_{i,2}=l_{j,3}\). Dashed lines denote added edges. Figure 5: Subgraph connections where \(l_{i,1}=l_{j,2}\) and \(l_{i,2}=l_{j,3}\). Dashed lines denote added edges. As can be seen from Figure 3, the maximum size of an independent set in the nine-vertex subgraph produced from the \(i\)th clause of \(E\) has size four, as realized either by \(x_{i,1}\), \(y_{i,2}\), \(y_{i,3}\), and \(z_{i,1}\), or by \(x_{i,2}\), \(y_{i,1}\), \(y_{i,3}\) a and \(z_{i,2}\), or by \(x_{i,3}\), \(y_{i,1}\), \(y_{i,2}\), and \(z_{i,3}\). Thus, each such subgraph must contribute exactly four vertices to \(I\), each partite set of \(G\) must contain at least one (in fact at least \(m\)) elements from \(I\), and only one element of \(I\) can be labeled by \(x\) in each subgraph. \(A\) is therefore a one-in-three truth assignment for \(E\), and \(A\) is valid as long as it contains no conflict (a literal set to true in one clause and false in another). Let us consider then the effect of a conflict between identical literals, \(l_{i,s}\) and \(l_{j,t}\), where \(i\
eq j\). Without loss of generality, suppose \(l_{i,s}\) is assigned true and \(l_{j,t}\) is assigned false under \(A\). This of course means that \(x_{i,s}\) is in \(I\) and \(x_{j,t}\) is not. Some \(x_{j,r}\), where \(r\
eq t\), must therefore be in \(I\).