# On Finding and Enumerating Maximal and Maximum \(k\)-Partite Cliques in \(k\)-Partite Graphs
## 5 A Special Class of Multipartite Graphs
In this section, we have further assumed knowledge of supplemental information about \(S\) and how its elements and subsets relate to a \(k\)-partite graph's vertices. Of course, \(S\) may not be unique. But what if it is not even known? In such an event, we first need to determine whether a \(k\)-partite graph is in fact a \(k\)-partite set intersection graph at all. Thus motivated, we now present a polynomial-time algorithm for this task, from which it follows that supplemental information about \(S\) is actually unneeded. We call this algorithm MSIGR, for multipartite set intersection graph recognition (see Algorithm 3), and base it on the following characterization. **Theorem 5**. : _Let \(G\) denote a \(k\)-partite graph. \(G\) is a \(k\)-partite set intersection graph if \(G\) contains some partite set \(P\) with the property that every pair of vertices in different partite sets other than \(P\) are either adjacent with a common neighbor in \(P\), or nonadjacent with no common neighbor in \(P\)._  
Proof of Theorem 5.: We first prove the forward (only if) implication. Let \(G\) denote an arbitrary \(k\)-partite set intersection graph. Then there exists some finite set \(S\) for which there is a partite set \(P\) containing only singleton vertices, one for each element of \(S\). Let \(u\) and \(v\) denote a pair of vertices that reside in different partite sets, neither of which is \(P\). If they are adjacent, then the subsets they represent share at least one element, which means they are adjacent to at least one common singleton vertex in \(P\) as well. On the other hand, if \(u\) and \(v\) are nonadjacent, then the subsets they represent are disjoint, and so they cannot be adjacent to a common singleton vertex in \(P\). We now prove the reverse (if) implication. Suppose we know only that \(G\) is a \(k\)-partite graph, with some partite set \(P\) satisfying the property stated in the theorem. Let \(p\) denote the cardinality of \(P\), and let \(S\) denote the set \(\{1,2,\ldots,p\}\). Associate with each vertex in \(P\) a unique element of \(S\), and associate with each vertex not in \(P\) the subset of \(S\) represented by all its neighbors in \(P\). Now suppose vertices \(u\) and \(v\) are adjacent. If either is in \(P\), then the sets they represent intersect by construction. If neither is in \(P\), then the fact that they must have a common neighbor in \(P\) means again that the sets they represent intersect. Conversely, suppose \(u\) and \(v\) are nonadjacent. If either is in \(P\), then the sets they represent are disjoint by construction. And if neither is in \(P\), then the fact that they must not have a common neighbor in \(P\) means again that the sets they represent are disjoint. \(G\) therefore satisfies the definition of a \(k\)-partite set intersection graph. ```
1 input: a \(k\)-partite graph \(G=(V,E)\), with partite sets \(V_{1}\), \(V_{2}\),..., \(V_{k}\);
2 output: \"yes\" or \"no,\" depending on whether \(G\) is a \(k\)-partite set intersection graph;
3 for each partite set \(P\) of \(G\)
4\(\mathit{flag}\leftarrow\mathit{true}\);
5 for every \(u\) and \(v\) in different partite sets, neither of which is \(P\)
6 if \(u\) and \(v\) are adjacent but have no common neighbor in \(P\)
7 then flag\(\leftarrow\mathit{false}\) and break for loop;
8 if \(u\) and \(v\) are nonadjacent but have a common neighbor in \(P\)
9 then flag\(\leftarrow\mathit{false}\) and break for loop;
10 if flag then report \"yes\" and halt;
11 report \"no\";
12 end MSIGR
```  
**Algorithm 3**MSIGR  
MSIGR's outer loop makes at most \(k\) iterations, while its inner loop performs \(O(n^{2})\) checks, each check against \(O(n)\) neighbors. MSIGR therefore runs in \(O(kn^{3})\) time.