<p>The problem is polynomial-time solvable.</p>
<p>Observe that we have to pick exactly one vertex from each color class to form a <span class="math-container">$k$</span>-clique.
If there is a vertex <span class="math-container">$x \in V_{i}$</span> that has no neighbor in some <span class="math-container">$V_{j}$</span> with <span class="math-container">$i \ne j$</span>,
then no <span class="math-container">$k$</span>-clique includes <span class="math-container">$x$</span>. Thus, we can remove such a vertex.
Repeat this until every vertex has a neighbor in each color class (except for the class it belongs to).
If some class becomes empty, then the graph does not have a <span class="math-container">$k$</span>-clique.
Otherwise, since the property ``every pair of color classes induces a biclique + isolated vertices''
is closed under taking induced subgraphs,
the remaining graph is a complete <span class="math-container">$k$</span>-partite graph, which contains a <span class="math-container">$k$</span>-clique.</p>

CC BY-SA 4.0
2020-09-09T10:15:49.577Z
Thank you for your effort. But, I am afraid the algorithm is wrong. I shall give the examples in the [chat room](https://chat.stackexchange.com/rooms/112808/discussion-on-multi-colored-clique-when-color-pairs-induce-bicliqueisolated-vert).
Cyriac Antony
CC BY-SA 4.0
2020-09-09T23:52:40.593Z
@CyriacAntony Do you still think the argument is incorrect? I see no flaw in my answer...
Yota Otachi
CC BY-SA 4.0
2020-09-10T05:47:53.757Z
Please consider mentioning time complexity at the end for completeness sake. Thanks.
Cyriac Antony
CC BY-SA 4.0
2020-09-09T05:49:59.757Z
2020-09-09T05:49:59.757Z
Yota Otachi
<p>I am interested in the <em>MulitColoredClique</em> problem with an additional restriction.<br />
(Def.: A <em><span class="math-container">$k$</span>-coloring</em> <span class="math-container">$V_1,V_2,\dots,V_k$</span> of a graph <span class="math-container">$G$</span> is a partition of the vertex set of <span class="math-container">$G$</span> into <span class="math-container">$k$</span> independent sets <span class="math-container">$V_1,V_2,\dots,V_k$</span>).</p>
<p><em>MulitColoredClique with Simple Modules</em><br />
Instance: A graph <span class="math-container">$G$</span>, an integer <span class="math-container">$k$</span>, and a <span class="math-container">$k$</span>-coloring <span class="math-container">$V_1,V_2,\dots,V_k$</span> of <span class="math-container">$G$</span> such that<br />
<span class="math-container">$\quad\qquad\;\ $</span>for every pair of colors <span class="math-container">$i$</span> and <span class="math-container">$j$</span>, <span class="math-container">$V_i\cup V_j$</span> induces the disjoint union of<br />
<span class="math-container">$\quad\qquad\;\ $</span> a complete bipartite graph with an independent set.<br />
(in other words, if <span class="math-container">$x\in V_i$</span> has a neighbor in <span class="math-container">$V_j$</span>, and <span class="math-container">$y\in V_j$</span> has a neighbor in <span class="math-container">$V_i$</span>, then <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are neighbors).<br />
Question: Is there a clique of size <span class="math-container">$k$</span> in <span class="math-container">$G\,?$</span></p>
<p><strong>Is this problem NP-hard?</strong>  (or even W[1]-hard?)<br />
I have a feeling that it is indeed NP-hard, but I am unable to prove it.<br />
Or, is this problem in P?<br />
If it is in P, an interesting combinatorial problem will also be in P.</p>
<p>Is this or any related problem (other than <em>MultiColoredClique</em>) studied in the literature?</p>
<p>PS: Sorry, I asked the wrong question. Somehow, I assumed that bipartite complement of biclique+isolated vertices was again biclique+isolated vertices. What I wanted to ask is here: <a href="https://cstheory.stackexchange.com/q/47543/47855">Complement of Multi-colored Clique with an extra condition</a></p>

CC BY-SA 4.0
2020-09-08T06:40:12.593Z
If $x \in V_i$ has no neighbor in $V_j$ ($i \ne j$), then $x$ cannot be in any $k$-clique. So you can remove it from the graph. Repeating this, you will end up with a trivial instance: a complete $k$-partite graph (which clearly contains a $k$-clique) or an empty graph.
Yota Otachi
CC BY-SA 4.0
2020-09-08T06:58:30.923Z
@YotaOtachi Note that $i$ and $j$ are fixed. eg: Suppose only 3 classes are there $V_1,V_2$ and $V_3$. Let $x\in V_1$. Even when $x$ has no neighbor in $V_2$, it can have neighbors in $V_3$.
Cyriac Antony
CC BY-SA 4.0
2020-09-08T07:02:33.390Z
Since we are looking for a clique of size $k$ in a $k$-colored graph, we need to pick one vertex from each color class $V_i$. So, each vertex picked into a $k$-clique has to have a neighbor in each color class.
Yota Otachi
CC BY-SA 4.0
2020-09-08T08:01:50.657Z
@YotaOtachi Just a moment. Then, the same method should be enough to find a solution to *MulticoloredClique* in poly. time, right? So, something is missing for sure.
Cyriac Antony
CC BY-SA 4.0
2020-09-09T00:30:10.520Z
No. You won't end up with a trivial instance in the general case. For example, consider a cycle of six vertices 1, 2, 3, 4, 5, 6 visiting them in this ordering, and partition the vertex set into {1,4}, {2,5}, {3,6}. Each vertex has a neighbor in every other color class, but this graph is clearly $K_3$ free.
Yota Otachi
CC BY-SA 4.0
2020-09-09T01:25:15.253Z
@YotaOtachi Please post your idea as an answer. By the way, I still don't understand *how* the additional condition makes a difference for your algorithm.
Cyriac Antony
CC BY-SA 4.0
2020-09-09T03:26:14.520Z
We could discuss in the chat room: https://chat.stackexchange.com/rooms/112808/discussion-on-multi-colored-clique-when-color-pairs-induce-bicliqueisolated-vert
Cyriac Antony
<cc.complexity-theory><graph-theory>
Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices
Cyriac Antony
# Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices

(Asked by: username_0 on 2020-09-07)

I am interested in the *MulitColoredClique* problem with an additional restriction.  
(Def.: A *$k$-coloring* $V\_1,V\_2,\dots,V\_k$ of a graph $G$ is a partition of the vertex set of $G$ into $k$ independent sets $V\_1,V\_2,\dots,V\_k$).

*MulitColoredClique with Simple Modules*  
Instance: A graph $G$, an integer $k$, and a $k$-coloring $V\_1,V\_2,\dots,V\_k$ of $G$ such that  
$\quad\qquad\;\ $for every pair of colors $i$ and $j$, $V\_i\cup V\_j$ induces the disjoint union of  
$\quad\qquad\;\ $ a complete bipartite graph with an independent set.  
(in other words, if $x\in V\_i$ has a neighbor in $V\_j$, and $y\in V\_j$ has a neighbor in $V\_i$, then $x$ and $y$ are neighbors).  
Question: Is there a clique of size $k$ in $G\,?$

**Is this problem NP-hard?** (or even W[1]-hard?)  
I have a feeling that it is indeed NP-hard, but I am unable to prove it.  
Or, is this problem in P?  
If it is in P, an interesting combinatorial problem will also be in P.

Is this or any related problem (other than *MultiColoredClique*) studied in the literature?

PS: Sorry, I asked the wrong question. Somehow, I assumed that bipartite complement of biclique+isolated vertices was again biclique+isolated vertices. What I wanted to ask is here: [Complement of Multi-colored Clique with an extra condition](https://cstheory.stackexchange.com/q/47543/47855)

**Tags:** cc.complexity-theory, graph-theory
> **Comments:**
> **username_1**: If $x \in V_i$ has no neighbor in $V_j$ ($i \ne j$), then $x$ cannot be in any $k$-clique. So you can remove it from the graph. Repeating this, you will end up with a trivial instance: a complete $k$-partite graph (which clearly contains a $k$-clique) or an empty graph.  
> **username_0**: @YotaOtachi Note that $i$ and $j$ are fixed. eg: Suppose only 3 classes are there $V_1,V_2$ and $V_3$. Let $x\in V_1$. Even when $x$ has no neighbor in $V_2$, it can have neighbors in $V_3$.  
> **username_1**: Since we are looking for a clique of size $k$ in a $k$-colored graph, we need to pick one vertex from each color class $V_i$. So, each vertex picked into a $k$-clique has to have a neighbor in each color class.  
> **username_0**: @YotaOtachi Just a moment. Then, the same method should be enough to find a solution to *MulticoloredClique* in poly. time, right? So, something is missing for sure.  
> **username_1**: No. You won't end up with a trivial instance in the general case. For example, consider a cycle of six vertices 1, 2, 3, 4, 5, 6 visiting them in this ordering, and partition the vertex set into {1,4}, {2,5}, {3,6}. Each vertex has a neighbor in every other color class, but this graph is clearly $K_3$ free.  
> **username_0**: @YotaOtachi Please post your idea as an answer. By the way, I still don't understand *how* the additional condition makes a difference for your algorithm.  
> **username_0**: We could discuss in the chat room: https://chat.stackexchange.com/rooms/112808/discussion-on-multi-colored-clique-when-color-pairs-induce-bicliqueisolated-vert  

---

## 1 answers

### Answer by username_1 on 2020-09-09. Score: 3 | Accepted answer

The problem is polynomial-time solvable.

Observe that we have to pick exactly one vertex from each color class to form a $k$-clique.
If there is a vertex $x \in V\_{i}$ that has no neighbor in some $V\_{j}$ with $i \ne j$,
then no $k$-clique includes $x$. Thus, we can remove such a vertex.
Repeat this until every vertex has a neighbor in each color class (except for the class it belongs to).
If some class becomes empty, then the graph does not have a $k$-clique.
Otherwise, since the property ``every pair of color classes induces a biclique + isolated vertices''
is closed under taking induced subgraphs,
the remaining graph is a complete $k$-partite graph, which contains a $k$-clique.

> **Comments:**
> **username_0**: Thank you for your effort. But, I am afraid the algorithm is wrong. I shall give the examples in the [chat room](https://chat.stackexchange.com/rooms/112808/discussion-on-multi-colored-clique-when-color-pairs-induce-bicliqueisolated-vert).  
> **username_1**: @CyriacAntony Do you still think the argument is incorrect? I see no flaw in my answer...  
> **username_0**: Please consider mentioning time complexity at the end for completeness sake. Thanks.  

---

