Reduction from MAX-3-CUT to MAX-CUT

Question

Both MAX-CUT and MAX-3-CUT are known to be NP-complete. This post shows a reduction from MAX-CUT to MAX-3-CUT. I am curious if there is a way to reduce MAX-3-CUT to MAX-CUT?

MAX-CUT: Given an undirected graph $G=(V,E)$, a weight function $w:E\to\mathbb{N}$, and $k\in\mathbb{N}$, determine if there exists a partition $(V_1,V_2)$ of $V$ (that is, $V_1\cap V_2=\emptyset$ and $V_1\cup V_2=V$) such that $$ \sum_{(u,v)\in V_1\times V_2}w(u,v)\ge k. $$

MAX-$3$-CUT: Given an undirected graph $G=(V,E)$, a weight function $w:E\to\mathbb{N}$, and $k\in\mathbb{N}$, determine if there exists a tri-partition $(V_1,V_2,V_3)$ of $V$ (that is, $V_1\cap V_2=V_1\cap V_3=V_2\cap V_3=\emptyset$ and $V_1\cup V_2\cup V_3=V$) such that $$ \sum_{(u,v)\in V_1\times V_2}w(u,v)+\sum_{(u,v)\in V_1\times V_3}w(u,v)+\sum_{(u,v)\in V_2\times V_3}w(u,v)\ge k. $$

I do not have a good idea of what a reasonable reduction approach would look like. It seems to me that going from a tri-partition to a partition would necessarily involve merging two subsets into one, but I am not sure how this can be done without losing information on the tri-partition. Any help is appreciated.

Answer 1

We want to use a $\textsf{MAX-CUT}$ algorithm to solve the $\textsf{MAX-3-CUT}$ problem. Therefore we need to transform our original graph $G$ into a new graph $G'$ in such a way that finding a max-cut on $G'$ tells us how to cut $G$ into 3.

Let's start by creating, for every $v \in V(G)$ three vertices $v_A, v_B, v_C \in V(G')$. We will say $v_A, v_B$ and $v_C$ are vertices of type $v$ in $G'$. We will design $G'$ in such a way that exactly one vertex of type $v$ is on the left side $V_1$ of $\textsf{MAX-CUT}(G')$, which will naturally tell us how $G$ should have been cut into $3$ parts.

To do that, we will design $G'$ such that the value of $\textsf{MAX-CUT}(G')$ can be separated into two parts; one natural part of value $K$ corresponding to the value of $\textsf{MAX-3-CUT}(G)$, and one artificial part $P$ corresponding to additional edges of $G'$.

If for every $v \in V(G)$ we add edges of a weight $W$ which will be guaranteed to be much larger than $K$ (e.g., $ W = |V| \cdot \sum_{e \in E(G)} w(e) \geq |V| \cdot K $) to $G'$ between each pair of vertices of type $v$, then the $\textsf{MAX-CUT}(G')$ will definitely separate 2 of the vertices of type $v$ from the 3rd.

Let us now enforce that all the groups of $2$ vertices of type $v$ will be on the same side. For this, create a special vertex $S$ that is connected to all other vertices of $G'$ by edges of weight $W' := \frac{W}{{|G|}}$. Assume without loss of generality that $V_1$ is the part of $\textsf{MAX-CUT}(G')$ where vertex $S$ ends up, and observe now that all groups of $2$ vertices of the same type must be in $V_2$, as otherwise swapping them from $V_1$ to $V_2$ would increase the artificial part of the cut-value by $W'$, which is more than whatever loss it could incur in terms of the natural value $K$. Note as well that it is not convenient to have the $3$ vertices of the same type on $V_2$, as that would gain only $\frac{W}{{|G|}}$ by edges toward $S$, while losing two edges of weight $W$ between the vertices of the given type.

Now, given we can safely assume $V_1$ will contain exactly one vertex per type, for each edge $(u,v)$ of weight $w$ in $G$ we add edges $(u_A, v_A)$, $(u_B, v_B)$ and $(u_C, v_C)$ of weight $w/2$ in $G'$. That way, if $u_X \in V_1 \land v_{Y} \in V_1$ for some $X \neq Y \in \{A, B, C\}$, then $w$ should be part of the natural value of the cut, which is indeed achieved as now $u_Y \in V_2$ and $v_X \in V_2$. On the other hand, if $u_X \in V_1 \land v_X \in V_1$, then none of these additional edges is in the cut, which matches $u$ and $v$ being on the same part of $\textsf{MAX-3-CUT}(G)$.

This way, there will be a cut of value $K + 2|V(G)|W + 2|V(G)|W'$ in $G'$ iff there was a 3-cut of value $K$ in $G$.