3
$\begingroup$

MAX-3-CUT gets a graph and a number $k$, and determines whether three sets of vertices can be found within that graph, where at least $k$ edges are in the cut. We define the cut as all edges $(u,v)$ where $u$ and $v$ are in a different set.

MAX-CUT also gets a graph and a number $k$, and does the same but by dividing it to two sets of vertices.

It is known that MAX-CUT is NP complete and I'm trying to show that MAX-3-CUT is also NP Complete by reducing from MAX-CUT.

What I've done so far:

  1. Showing that MAX-3-CUT in NP is easy using a verifier.

  2. I think the reduction should be, given $\langle G=(V,E),k \rangle$ return $\langle G',k+|V| \rangle$, where $G'=(V'=V+{w}, E'=E+\{(w,v) : v \in V\})$.

  3. Proof of correctness: doing so, It's easy to show that if $\langle G,K \rangle$ is in MAX-CUT then $\langle G',k+|V| \rangle$ is in MAX-3-CUT by setting the third group to be $\{w\}$. The problem is I can't do the opposite direction: if $\langle G,k \rangle$ isn't in MAX-CUT than $\langle G',k+|V| \rangle$ isn't in MAX-3-CUT. I also tried to show that if $\langle G',k' \rangle$ is in MAX-3-CUT then $\langle G,k \rangle$ is in MAX-CUT but I get stuck with how to turn 3 sets into 2.

Note: I was able to show that MAX-3-CUT is NPC by reducing from 3COL (pretty straightforward), but I need it to be reduced from MAX-CUT.

$\endgroup$
  • 1
    $\begingroup$ I suggest you continue trying. Perhaps your current reduction just doesn't work. In any case, you can try constructing a different one whose correctness is easier to prove. $\endgroup$ – Yuval Filmus Dec 8 '16 at 15:16
1
$\begingroup$

Hint : Consider $G '=(V'=V \cup\{w_i|i\in [1,|V|]\},E'=E\cup\{(w_i,v)|v \in V , i\in [1,|V|]\})$ and $k'=|V|^2+k $

Consider a partition of V' in 3 parts, call $P $ the one with the smallest number of nodes in $V $.

Note that by putting a w in P , if it were not in it, you increase the number of edges in your 3cut.

Then, note that if all the ws are in the same part, then removing a node of V from that part increases the number of edges in your 3cut.

$\endgroup$

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.