The Two Clique problem is in P or NP? P != NP for hypothesis.

Question

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?

Answer 1

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:

1. Color all vertices gray.
2. Choose some initial vertex $v_0$ and color it white.
3. If there are no more gray vertices, the graph is bi-partitie, as witnessed by its coloring.
4. If some white vertex has a white neighbour, the graph is not bipartite.
5. Color all gray vertices with a white neighbour black.
6. If some black vertex has a black neighbour, the graph is not bipartite.
7. Color all gray vertices with a black neighbour white.
8. 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 :).