I need to find a solution to the following question:
The problem of the "Two Clique" is in P or NP-complete (assuming P != NP)?
The "Two Clique" problem is the following:
Given a graph G = (V, E), can V be partitioned into two non-empty parts V1, V2 such that
V = V1 ∪ V2 and both V1 and V2 are cliques in G?
I was thinking about an approach based on an algorithm for bipartite graphs,
what do you think about it?
Best Answer
By taking the complement graph, i.e., replacing $E$ with $E'$ where $e \in E'$ iff $e \not\in E$, we get the related problem: Let $G = (V,E)$ be a graph. Can $V$ be partitioned into two non-empty parts such that $V1$ and $V2$ are independent sets?
This problem is then actually equivalent to asking whether $(V,E)$ is a bipartite graph. An approach to solve this could be the following:
Changing this to an algorithm for 2-Clique is straightforward, and it is easy to show that this algorithm runs in polynomial time.
Edit: The algorithm as stated deals only with the case where $(V,E)$ is connected. For non-connected graphs, add a step 7.5: If, in the last round of the algorithm, no vertex got a new color (i.e., in line 5 and 7, no change occured), choose any gray vertex and color it black or white.
A good choice of coloring strategy for the original problem is easy to find and left as an exercise to the reader :).