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

algorithmscomputational complexitynp-complete

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:

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

Related Question