I am interested in the complexity of the following problems:

Input: an undirected graph $G = \langle V, E \rangle$

Query 1: is there a partition of $V$ into two a clique $C$ and an independent set $I$ of equal size?

Query 2: are there a clique $C \subseteq V$ and an independent set $I \subseteq V$ whose sizes are at least $\frac{|V|}{4}$?

  • 1
    $\begingroup$ Your restrictions seem quite artificial. Anyway, you might be interested in knowing that graphs whose vertex set can be partitioned into a clique and an independent set are known as split graphs. They are all chordal, and can be recognized in linear time. $\endgroup$ – Juho Jun 12 '16 at 17:23
  • $\begingroup$ I removed the restriction. It seems the kind of restriction which is used for homework assignments, and homework assignments are off-topic here. See help center. You might want to check out our sister site Computer Science which has a boarder scope. $\endgroup$ – Kaveh Jun 12 '16 at 19:36

Question (1) is easy polynomial time. As Juho has already mentioned in comments, the graphs that can be partitioned into a clique and an independent set are the split graphs. They can be recognized and partitioned in polynomial time, and all valid partitions (if there are more than one) differ by only a single vertex and can also be found in polynomial time (see the Wikipedia article for details). So you simply test whether any of these partitions satisfies your additional constraint.

As for Question (2), it seems you already know that HALF-CLIQUE is NP-complete, so taking an n-vertex hard instance for this problem and adding another n independent vertices produces a hard instance for your problem. That is, the answer is that it is indeed NP-complete.
One could more-or-less mechanically compose this with the hardness reduction for HALF-CLIQUE to get a reduction from a SAT-like problem, but why is that an interesting or useful thing to do?


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.