The Two Clique problem is in P or NP? P != NP for hypothesis. 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?
 A: 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:


*

*Color all vertices gray.

*Choose some initial vertex $v_0$ and color it white.

*If there are no more gray vertices, the graph is bi-partitie, as witnessed
by its coloring.

*If some white vertex has a white neighbour, the graph is not bipartite.

*Color all gray vertices with a white neighbour black.

*If some black vertex has a black neighbour, the graph is not bipartite.

*Color all gray vertices with a black neighbour white.

*Go to step 4.


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 :).
