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?

  • 2
    $\begingroup$ What does the notation $\delta(G(V_1))$ mean? Also, please credit the source where you encountered this exercise. $\endgroup$
    – D.W.
    May 16 '18 at 6:30
  • 1
    $\begingroup$ "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. $\endgroup$ May 16 '18 at 14:19
  • $\begingroup$ "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. $\endgroup$ May 16 '18 at 14:21
  • $\begingroup$ @j_random_hacker yes, I just corrected it. $\endgroup$
    – Mengfan Ma
    May 16 '18 at 21:06
  • $\begingroup$ @xskxzr I’m sure it’s the maximum degree. But I’m not quite understand what you mean. Can you be more specific? $\endgroup$
    – 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: enter image description here

    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.

  • $\begingroup$ 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 ? $\endgroup$
    – Mengfan Ma
    May 23 '18 at 4:53
  • $\begingroup$ @Mark No, otherwise the rightmost unnamed vertex can be colored blue with all $u,v,w$ colored blue. $\endgroup$
    – xskxzr
    May 23 '18 at 5:48

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.