4
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – joro Mar 5 '15 at 12:46

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.