# Reduction from MAX-3-CUT to MAX-CUT

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

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