Modified Clique Problem

Question

We know CLIQUE and HALF-CLIQUE problems are NP-complete. Now consider the class of graphs (let's call it $\mathcal{G}_{2K}$) where a graph $G=(V,E)$ is a member of $\mathcal{G}_{2K}$ iff $G$ has two SEPARATE cliques $K_1$ and $K_2$ of size $\dfrac{N}{2}$ (where $|V| = N$). My speculation is that $\mathcal{G}_{2K}$ is in NP and the corresponding existential problem is NP-complete, but I can't find any reduction form any well-known NP-complete problem.

Hence the question is: Is $\mathcal{G}_{2K}$ in P or it's NP-complete?

The question I asked is equivalent to these two questions: 1. Given graph $G=(V,E)$ and integer $k$, can we partition the vertices into two disjoint cliques of size $k$ and $|V|-k$. 2. Given graph $G=(V,E)$ can we partition the vertices into two independent sets of size $k$ and $|V|-k$?

Answer 1

The problem is equivalent to deciding whether the complement graph of $G$ has a bipartition $(A,B)$ such that $|A|=|B|$. In order to check if such a bipartition exists, one can first compute an arbitrary bipartition $(A,B)$. If no such bipartition exists, we are finished. If it does exists, we must check whether we can flip single connected components of this bipartition (which mean all vertices in $A$ of a particular connected component are moved to $B$ and vice versa) such that we obtain a new partition where $A$ is equal to $B$. Using a dynamic programing approach similar to the partition problem, this can be decided in polynomial time. Thus the original problem is also in P and not NP-hard unless P equals NP.