# Modified Clique Problem

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$?

• It's certainly in NP: the vertex sets of the two cliques are a witness. – David Richerby Oct 26 '15 at 22:28
• Just to make sure I understand the definition: the fully connected graph would be in $\mathcal{G}_{2K}$, if the number of vertices is even, right? (In other words, you don't intend to impose any requirement that $K_1,K_2$ are the only two cliques of size $\ge |V|/2$, right?) – D.W. Oct 26 '15 at 23:25
• Yes the problem is obviously in NP, also partition $(K_1, K_2)$ is not unique. – Saaber Oct 27 '15 at 18:15
• The question I asked is equivalent to this question: Given graph $G=(V,E)$ and integer $k$, can we partition the vertices into two disjoint cliques of size $k$ and $|V|-k$. Or equivalently given graph $G=(V,E)$ can we partition the vertices into two independent sets of size $k$ and $|V|-k$? – Saaber Oct 27 '15 at 18:15

## 1 Answer

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.