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

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?

• What does the notation $\delta(G(V_1))$ mean? Also, please credit the source where you encountered this exercise. – D.W. May 16 '18 at 6:30
• "I'm quite lost as to ... which known NP-complete problem to use for the reduction" How many have you encountered so far in the course? If it's a short list, you might consider adding it to the question. – Peter Taylor May 16 '18 at 14:19
• "such that $\delta(G(V_1))\le 2$ and $\delta(G(V_1))\le 3$" -- I think you meant $V_2$ in the second term, since otherwise it's redundant. – j_random_hacker May 16 '18 at 14:21
• @j_random_hacker yes, I just corrected it. – Mengfan Ma May 16 '18 at 21:06
• @xskxzr I’m sure it’s the maximum degree. But I’m not quite understand what you mean. Can you be more specific? – Mengfan Ma May 20 '18 at 6:51

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.

• Can we use the same structure in the second construction as the one in the first construction, which has ensured all the unnamed vertices are red ? – Mengfan Ma May 23 '18 at 4:53
• @Mark No, otherwise the rightmost unnamed vertex can be colored blue with all $u,v,w$ colored blue. – xskxzr May 23 '18 at 5:48