<p>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 <a href="https://en.wikipedia.org/wiki/Split_graph">split graphs</a>. 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.</p>

<p>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.<br>
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?</p>

CC BY-SA 3.0
2016-06-12T18:54:13.357Z
2016-06-12T19:38:12.113Z
2016-06-12T19:38:12.113Z
David Eppstein
<p>I am interested in the complexity of the following problems:</p>

<p><strong>Input</strong>: an undirected graph $G = \langle V, E \rangle$</p>

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

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

CC BY-SA 3.0
2016-06-12T17:23:03.703Z
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.
Juho
CC BY-SA 3.0
2016-06-12T19:36:40.410Z
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/on-topic]. You might want to check out our sister site [cs.se] which has a boarder scope.
Kaveh
<cc.complexity-theory><ds.algorithms><graph-theory><clique><independent-set>
Paritioning a graph into clique and independent set
socumbersome
# Paritioning a graph into clique and independent set

(Asked by: username_0 on 2016-06-12)

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

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, clique, independent-set

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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/on-topic]. You might want to check out our sister site [cs.se] which has a boarder scope.  

---

## 1 answers

### Answer by username_3 on 2016-06-12. Score: 6 | Accepted answer

Question (1) is easy polynomial time. As username_1 has already mentioned in comments, the graphs that can be partitioned into a clique and an independent set are the [split graphs](https://en.wikipedia.org/wiki/Split_graph). 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?


---

