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

Improve this question
$\endgroup$
7
  • 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, 2020 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, 2020 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, 2020 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, 2020 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, 2020 at 0:30

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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, 2020 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, 2020 at 23:52
  • $\begingroup$ Please consider mentioning time complexity at the end for completeness sake. Thanks. $\endgroup$
    – Cyriac Antony
    Sep 10, 2020 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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