In the problem Multi-colored clique, we ask for a $k$-clique of the input graph $G$ where $G$ is guaranteed to be $k$-colorable. In the complement problem Independent Set given Clique Partition, we ask for a $k$-independent set of the input graph which admits a $k$-clique partition.

Independent Set given Clique Partition with Simple Modules
Instance: A graph $G$, a +ve integer $k$, a partition of vertex set of $G$ into cliques $V_1,V_2,\dots,V_k$
$\qquad \quad\,$ such that for every pair of colors $i$ and $j$, $V_i\cup V_j$ induce a clique plus isolated vertices
$\qquad \quad\,$ (that is, if $x\in V_i$ has a neighbor in $V_j$, and $y\in V_j$ has a neighbor in $V_i$,
$\qquad \quad\,$ then $x$ and $y$ are neighbors).
Question: Is there an indepedent set of size $k$ in $G\,?$

(NB: "clique plus isolated vertices" refer to the disjoint union of a clique and a set of isolated vertices)

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? Is the condition ''each color pair induce biclique+isolated vertices'', or something similar considered in a study?

Note: I asked the following question first: Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices. But, my actual interest is in the problem described above.

  • $\begingroup$ Are you sure that each part $V_i$ should be a clique? If yes, then the size of each part is restricted to at most 2 since $G[V_i]$ is bipartite given the constraints on $G[V_i\cup V_j]$. $\endgroup$ Sep 11, 2020 at 11:24
  • $\begingroup$ @ChristianKomusiewicz Oops, the condition is wrong. I shall correct it. $\endgroup$ Sep 11, 2020 at 13:29
  • 1
    $\begingroup$ I think this problem is best re-phrased as a CSP. I’m pretty sure it is NP-complete (see the CSP dichotomy theorem) already when each Vi has size 3 and should be pretty easy to show FPT parameterized by k. $\endgroup$
    – daniello
    Sep 14, 2020 at 23:33


Your Answer

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

Browse other questions tagged or ask your own question.