Max-Cut-Multi ≤p Max-Cut | Complexity Atlas

The construction

Let $G=(V,E)$ be a multigraph. Define $G'=(V',E')$ :

Vertices: $V'=V\cup V''$ , where each edge $\{u,v\}\in E$ contributes two vertices $u',v'$ unique to that edge.
Edges: for each original edge $\{u,v\}$ , the three edges $\{u,u'\},\quad\{u',v'\},\quad\{v',v\}.$

So each edge is replaced by a path of length $3$ through two private new vertices. The output is $\langle G',\ 2|E|+k\rangle$ .

$G'$ is simple. Two parallel edges $\{u,v\}$ receive four distinct intermediate vertices, so their paths are internally disjoint and no parallel edges arise; a loop $\{u,u\}$ likewise becomes a path through two new vertices and ceases to be a loop.

Visualization

|E| = 4k = 3

original vertex of V

Correctness — both directions

Max-Cut-Multi ∈ ⟹ Max-Cut ∈

Suppose $G$ has a cut $(U,\bar U)$ of size at least $k$ . Build a cut in $G'$ with at least $2|E|+k$ edges.

Start from $U'\supseteq U$ (old vertices keep their sides) and fix the intermediate vertices edge by edge. Let $\{u,v\}\in E$ with intermediates $u',v'$ .

If the edge crosses ( $u,v$ on different sides): put $u'$ on $v$ 's side and $v'$ on $u$ 's side. Then all three edges $\{u,u'\},\{u',v'\},\{v',v\}$ cross — contribution $3$ .
If the edge does not cross ( $u,v$ on the same side): put $u'$ on the opposite side and $v'$ on $u,v$ 's side. Then $\{u,u'\}$ crosses, $\{u',v'\}$ crosses, and $\{v',v\}$ does not — contribution $2$ .

So every edge contributes at least $2$ , and every crossing edge contributes $3$ . If the original cut had $c\ge k$ crossing edges, the total is $2(|E|-c)+3c=2|E|+c\;\ge\;2|E|+k .$ Hence $\langle G',2|E|+k\rangle\in\mathrm{Max\text{-}Cut}$ .

Max-Cut ∈ ⟹ Max-Cut-Multi ∈

Suppose $G'$ has a cut $(W,\bar W)$ of size at least $2|E|+k$ . Define $U=W\cap V$ — restrict the cut to the old vertices — and show the induced cut in $G$ has at least $k$ edges.

The local bound. Let $\{u,v\}\in E$ with its intermediate path. Count how many of the path's three edges can cross, depending only on the sides of $u$ and $v$ :

if $u,v$ are on the same side of $W$ : the path $u\to u'\to v'\to v$ starts and ends on one side, so the number of crossings along it is even — that is $0$ or $2$ . In particular at most $2$ .
if $u,v$ are on different sides: the number of crossings along the path is odd — $1$ or $3$ . In particular at most $3$ .

(The argument is just tracking side changes along a path: the number of changes is even iff the two endpoints share a side.)

The count. Let $c$ be the number of edges of $G$ whose endpoints lie on different sides of $W$ — exactly the crossing edges of $(U,\bar U)$ in $G$ . The total number of crossing edges in $G'$ is bounded by $2(|E|-c)+3c=2|E|+c .$ On the other hand the cut in $G'$ was assumed to have at least $2|E|+k$ edges. Hence $2|E|+k\;\le\;2|E|+c\quad\Longrightarrow\quad c\;\ge\;k .$

So $G$ has a cut of size at least $k$ , i.e. $\langle G,k\rangle\in\mathrm{Max\text{-}Cut\text{-}Multi}$ .

Cost of the reduction

TimeO(|V| + |E|)

SpaceO(|V| + |E|)

Output size|V| + 2|E| vertices, 3|E| edges

A single pass over the edges: two new vertices and three edges each. The threshold $2|E|+k$ is one addition. The output is linear in the input size.

What it buys

With the trivial reduction the other way ( $\mathrm{Max\text{-}Cut}\le_p\mathrm{Max\text{-}Cut\text{-}Multi}$ — a simple graph is a multigraph), the two problems are polynomially equivalent. Hence $\mathrm{Max\text{-}Cut}$ on simple graphs is NP-complete, even though the reduction from $\mathrm{3NAE}$ produces a multigraph.

Pitfalls

The intermediate vertices must be private to their edge. Were two parallel edges to share intermediates, $G'$ would not be simple — which is the entire point of the construction.
The threshold is not $k$ but $2|E|+k$ . Every edge pays a "tax" of $2$ regardless, and only the third crossing carries information. Forgetting the tax breaks both directions.

The chain

Rests on

3NAE ≤p MAXCUT

Where this was read from

2026"Prove $G'$ is simple, and that $G$ has a cut of size at least $k$ iff $G'$ has one of size at least $2|E|+k$ ."
2024The same construction, phrased as "adding two new vertices per edge".
2025The same construction on a multigraph with parallel edges and loops.
2026 $\mathrm{Max\text{-}Cut\text{-}Simple}$ against the multigraph version.

This reduction does not appear in the 2026B lessons — lesson 10 stops at the multigraph and flags the question as a class exercise. It has been examined in at least four sittings, and the construction above is copied from the phrasing the papers themselves give.