<p>In the problem Multi-colored clique, we ask for a <span class="math-container">$k$</span>-clique of the input graph <span class="math-container">$G$</span> where <span class="math-container">$G$</span> is guaranteed to be <span class="math-container">$k$</span>-colorable. In the complement problem <em>Independent Set given Clique Partition</em>, we ask for a <span class="math-container">$k$</span>-independent set of the input graph which admits a <span class="math-container">$k$</span>-clique partition.</p>
<p><em>Independent Set given Clique Partition with Simple Modules</em><br />
Instance: A graph <span class="math-container">$G$</span>, a +ve integer <span class="math-container">$k$</span>, a partition of vertex set of <span class="math-container">$G$</span> into cliques <span class="math-container">$V_1,V_2,\dots,V_k$</span><br />
<span class="math-container">$\qquad \quad\,$</span> such that 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> induce a clique plus isolated vertices<br />
<span class="math-container">$\qquad \quad\,$</span> (that is, 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>,<br />
<span class="math-container">$\qquad \quad\,$</span> then <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are neighbors).<br />
Question: Is there an indepedent set of size <span class="math-container">$k$</span> in <span class="math-container">$G\,?$</span></p>
<p>(NB: &quot;clique plus isolated vertices&quot; refer to the disjoint union of a clique and a set of isolated vertices)</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? Is the condition ''each color pair induce biclique+isolated vertices'', or something similar considered in a study?</p>
<p>Note: I asked the following question first: <a href="https://cstheory.stackexchange.com/q/47526/47855">Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices</a>. But, my actual interest is in the problem described above.</p>

CC BY-SA 4.0
2020-09-11T11:24:30.337Z
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]$.
Christian Komusiewicz
CC BY-SA 4.0
2020-09-11T13:29:05.887Z
@ChristianKomusiewicz Oops, the condition is wrong. I shall correct it.
Cyriac Antony
CC BY-SA 4.0
2020-09-14T23:33:32.037Z
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.
daniello
<cc.complexity-theory><graph-theory>
Complement of Multi-colored Clique with an extra condition
Cyriac Antony
# Complement of Multi-colored Clique with an extra condition

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

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](https://cstheory.stackexchange.com/q/47526/47855). But, my actual interest is in the problem described above.

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_1**: 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]$.  
> **username_0**: @ChristianKomusiewicz Oops, the condition is wrong. I shall correct it.  
> **username_2**: 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.  

---

## 0 answers

