# Reduction from PARTITION to MAX-CUT

I am trying to prove the NP-Hardness of the MAX-CUT problem. Other sources seem to reduce from the NAE-3SAT problem, however I have been trying to reduce from PARTITION because PARTITION and MAX-CUT are both in Karp's list of 21 NP-Complete problems and this is the reduction that he did [1].

PARTITION: Given ($c_1,c_2,\dots,c_n)\in\mathbb{Z}^n$, does there exist $S\subseteq\{1,2,\dots,n\}$ such that $$\sum_{i\in S}c_i=\sum_{j \not\in S}c_j$$

MAX-CUT: Given a weighted graph $G=(V,E)$ with weight function $w:E\rightarrow\mathbb{Z}$ and a target weight $W\in\mathbb{Z}^+$, does there exists $S\subseteq V$ such that $$\sum_{(u,v)\in E\::\:u\in S,\,v \not\in S}w((u,v))\geq W$$

After spending a lot of time trying to construct a reduction to prove PARTITION $\leq_p$ MAX-CUT myself, I eventually gave up and looked at Karp's paper. The problem I could not manage to solve is how you encode the equality constraint of PARTITION in a MAX-CUT instance which only has one inequality constraint. The reduction that Karp gives (which I would not have been able to come up with) is as follows:

Given a PARTITION instance $(c_1,c_2,\dots,c_n)$, construct a MAX-CUT instance $(G=(V,E),\,w,\,W)$ such that: $$V=\{1,2,\dots,n\}$$ $$E=\{(u,v) \: : \: i,j\in V,\, u\neq v\}$$ $$\forall (u,v) \in E,\,w((u,v))=c_ic_j$$ $$W=\lceil \frac{1}{4} \sum_{i=1}^{n}c_i^2\rceil$$

I am having trouble proving the correctness of this reduction (the paper does not seem to give any justification). I can kind of appreciate the need to be squaring values - is my intuition correct that this is to account for needing to the equality constraint with an inequality constraint?

I have tried using the Cauchy–Schwarz inequality to prove this with no luck. Similarly, I have tried to relate this to the variance/covariance of two partition sets, but I'm not sure if this is helping me understand why this reduction works.

A proof plus any intuition of how one might have arrived at this reduction would be greatly appreciated.

[1] Richard M. Karp (1972). "Reducibility Among Combinatorial Problems". In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. (pdf)

Since the graph is complete, any set $S$ will induce a cut of weight
$$\sum_{i\in S, j\notin S} c_ic_j ~~=~~ \sum_{i\in S} c_i \cdot \sum_{j\notin S} c_j.$$
Denote the two sums in the latter formula by $A$ and $B$. The problem of finding a maximal cut then means maximizing $A\cdot B$, while $A+B$ is fixed. It is well-known that the maximum of this product is achieved for $A=B$. In this case the product becomes $\left(\frac 12 \sum_{i=1}^n c_i\right)\cdot \left(\frac 12 \sum_{i=1}^n c_i\right) = \frac 14 \left(\sum_{i=1}^n c_i\right)^2$. So $W$ should not be a quarter of the sum of squares, but a quarter of the square of the sum.