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.


1 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.