<p>Computing a maximum clique in a graph whose vertex set can be partitioned into 3 cliques, is equivalent to computing a maximum independent set in the complement graph, which can be partitioned into 3 independent sets and is therefore 3-colorable. The latter problem is still NP-complete, which can be seen as follows: Start from an arbitrary instance $(G,k)$ of independent set and subdivide each edge twice, i.e., replace each edge ${u,v}$ by a path ${u,e_1, e_2, v}$ on two new vertices. It is not difficult to prove that the resulting graph $G'$ has an independent set of size $k + |E(G)|$ if and only if $G$ has a size-$k$ independent set: for every independent set in $G$, you can add exactly one of the two subdivider vertices on every edge without violating independence.</p>

<p>Hence the Clique problem is still NP-complete for such inputs.</p>

CC BY-SA 3.0
2015-03-05T12:46:32.410Z
Thank you. Maybe it will be more explicit to show the sets A,B,C are {u,v},{e_1},{e_2} in the complement.
joro
CC BY-SA 3.0
2015-03-05T12:27:55.197Z
2015-03-05T12:27:55.197Z
Bart Jansen
<p>A graph is <span class="math-container">$(p,q)$</span>-colorable if its vertices can be partitioned
into <span class="math-container">$p$</span> cliques and <span class="math-container">$q$</span> independent sets.</p>
<p>For <span class="math-container">$(2,0)$</span>-colorable graphs clique is polynomial.</p>
<p>I am interested how easier (if any) is clique in <span class="math-container">$(3,0)$</span>-colorable,
when the partitions are given.</p>
<p>Given graph <span class="math-container">$G$</span> and 3 partitions of its vertices
<span class="math-container">$A,B,C : A \cup B \cup C=V(G)$</span> such
that <span class="math-container">$A,B,C$</span> induce cliques in G.</p>
<blockquote>
<p>Q1 Is clique faster in this case?</p>
<p>Q2 If it is faster what is the complexity?</p>
<p>Q3 How good can we approximate clique in this case?</p>
</blockquote>
<p>We have a clique <span class="math-container">$\frac{V(G)}{3}$</span> for free.</p>

<graph-theory><graph-algorithms>
Does it help for clique if the vertices are partitioned into 3 cliques?
joro
# Does it help for clique if the vertices are partitioned into 3 cliques?

(Asked by: username_0 on 2015-03-05)

A graph is $(p,q)$-colorable if its vertices can be partitioned
into $p$ cliques and $q$ independent sets.

For $(2,0)$-colorable graphs clique is polynomial.

I am interested how easier (if any) is clique in $(3,0)$-colorable,
when the partitions are given.

Given graph $G$ and 3 partitions of its vertices
$A,B,C : A \cup B \cup C=V(G)$ such
that $A,B,C$ induce cliques in G.

> Q1 Is clique faster in this case?
>
> Q2 If it is faster what is the complexity?
>
> Q3 How good can we approximate clique in this case?

We have a clique $\frac{V(G)}{3}$ for free.

**Tags:** graph-theory, graph-algorithms

---

## 1 answers

### Answer by username_1 on 2015-03-05. Score: 11

Computing a maximum clique in a graph whose vertex set can be partitioned into 3 cliques, is equivalent to computing a maximum independent set in the complement graph, which can be partitioned into 3 independent sets and is therefore 3-colorable. The latter problem is still NP-complete, which can be seen as follows: Start from an arbitrary instance $(G,k)$ of independent set and subdivide each edge twice, i.e., replace each edge ${u,v}$ by a path ${u,e\_1, e\_2, v}$ on two new vertices. It is not difficult to prove that the resulting graph $G'$ has an independent set of size $k + |E(G)|$ if and only if $G$ has a size-$k$ independent set: for every independent set in $G$, you can add exactly one of the two subdivider vertices on every edge without violating independence.

Hence the Clique problem is still NP-complete for such inputs.

> **Comments:**
> **username_0**: Thank you. Maybe it will be more explicit to show the sets A,B,C are {u,v},{e_1},{e_2} in the complement.  

---

