2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yota Otachi Sep 8 at 6:40
  • $\begingroup$ @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$. $\endgroup$ – Cyriac Antony Sep 8 at 6:58
  • $\begingroup$ 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. $\endgroup$ – Yota Otachi Sep 8 at 7:02
  • $\begingroup$ @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. $\endgroup$ – Cyriac Antony Sep 8 at 8:01
  • $\begingroup$ 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. $\endgroup$ – Yota Otachi Sep 9 at 0:30
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your effort. But, I am afraid the algorithm is wrong. I shall give the examples in the chat room. $\endgroup$ – Cyriac Antony Sep 9 at 10:15
  • $\begingroup$ @CyriacAntony Do you still think the argument is incorrect? I see no flaw in my answer... $\endgroup$ – Yota Otachi Sep 9 at 23:52
  • $\begingroup$ Please consider mentioning time complexity at the end for completeness sake. Thanks. $\endgroup$ – Cyriac Antony Sep 10 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.