Is it NP hard to partition a graph into 2 vertex sets with minimum degree of 2 and 3?

Question

The following problem is from my algorithms class:

Given a graph $G=(V, E)$, decide whether a partition of $V=(V_1, V_2)$ exists such that $\delta(G(V_1))\ge 2 $ and $\delta(G(V_2))\ge 3 $, where $G(V_1)$ denotes the subgraph induced by $V_1$ and $\delta(G(V_1))$ denotes the minimum degree of graph $G(V_1)$. Prove this decision problem is NP complete.

I'm trying to prove $$\text{PARTITION} \le_p \text{This-Problem}$$ but haven't came up with a solution until now. I've never met a problem dealing with the minimum depth of a graph. Is there any theorem about it? Could anyone help me out here?

Answer 1

For convenience of description, we consider the problem as a coloring problem where vertices in $V_1$ are colored red and vertices in $V_2$ are colored blue.

The following is a reduction from 3SAT.

For any instance of 3SAT with $n$ variables (assume $n\ge 4$ without loss of generality), construct a complete graph of $2n$ vertices $V=\{v_1^0, v_1^1, \ldots, v_n^0, v_n^1\}$ where $v_i^0, v_i^1$ respectively represent the positive and negative literals of the $i$th variable. We also add some additional structures. Note that only named vertices can be in more than one structure.

1. For each $i$, add the following structure (note I emit the edges among named vertices and the same below):

   This structure ensures all the unnamed vertices are colored red, and at least one of $v_i^0$ and $v_i^1$ must be colored red.

2. For each clause $l_1\vee l_2\vee l_3$, say their corresponding vertices are $u,v,w\in V$, add the following structure:

   This structure ensures all the unnamed vertices are colored red, and at least one of $u,v,w$ must be colored red.

3. For each $i$, for each pair of vertices $\{u,v\}\subseteq V$, add the following structure:

   If both $v_i^0$ and $v_i^1$ are colored red, then all the unnamed vertices must be colored red, and at least one of $u$ and $v$ are colored red. Note this holds for all pairs $\{u,v\}$, so if both $v_i^0$ and $v_i^1$ are colored red, there are at most one vertex colored blue, which is impossible. As a result, this structure ensures at least one of $v_i^0$ and $v_i^1$ is colored blue. Combined with the first type of structures, it is ensured that $v_i^0$ and $v_i^1$ are colored different colors.

Now if there is a proper coloring, exactly one of $v_i^0$ and $v_i^1$ is colored red. If it is $v_i^0$, assign the $i$th variable 1, otherwise 0, then the assignment is a valid assignment for the 3SAT instance.

On the other hand, if there is a valid assignment for the 3SAT instance, color $v_i^0$ red and $v_i^1$ blue if the $i$th variable is assigned 1, otherwise color $v_i^0$ blue and $v_i^1$ red. Note the subgraph induced by $\{v_1^0, v_1^1, \ldots, v_n^0, v_n^1\}$ is a complete graph, this is a legal coloring. All unnamed vertices in the first two kinds of structures are colored red, and for a structure of the third type, if both $u$ and $v$ are colored blue, color all the three unnamed vertices blue, otherwise color them red. This is a proper coloring. Q.E.D.