6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ It's certainly in NP: the vertex sets of the two cliques are a witness. $\endgroup$ – David Richerby Oct 26 '15 at 22:28
  • $\begingroup$ 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?) $\endgroup$ – D.W. Oct 26 '15 at 23:25
  • $\begingroup$ Yes the problem is obviously in NP, also partition $(K_1, K_2)$ is not unique. $\endgroup$ – Saaber Oct 27 '15 at 18:15
  • $\begingroup$ 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$? $\endgroup$ – Saaber Oct 27 '15 at 18:15
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.