# reduction from MAX-CUT to MAX-3-CUT

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.

• 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. – Yuval Filmus Dec 8 '16 at 15:16

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$.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9315256,"math_prob":0.99501765,"size":1322,"snap":"2020-10-2020-16","text_gpt3_token_len":402,"char_repetition_ratio":0.17147192,"word_repetition_ratio":0.050847456,"special_character_ratio":0.30408472,"punctuation_ratio":0.10828026,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9996039,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-04-04T19:37:28Z\",\"WARC-Record-ID\":\"<urn:uuid:a4f89f3a-6f53-45ec-b70b-53ad7c4a15f5>\",\"Content-Length\":\"141723\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:c969621a-be46-48a7-8031-273a8c557b8c>\",\"WARC-Concurrent-To\":\"<urn:uuid:d9b49bf2-8a13-47d0-ab0d-de721c931ecc>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/67066/reduction-from-max-cut-to-max-3-cut\",\"WARC-Payload-Digest\":\"sha1:GJ33KYQLKOPZ4S7Q7UXOK437Q73F3H4K\",\"WARC-Block-Digest\":\"sha1:KG6CMZPP3DEIE7JBS7USF6MXPT25ZN2W\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-16/CC-MAIN-2020-16_segments_1585370524604.46_warc_CC-MAIN-20200404165658-20200404195658-00345.warc.gz\"}"}