[Solved]: Reduction from PARTITION to MAX-CUT

Problem Detail: 

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)

Asked By : Dave White

Answered By : FrankW

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.

So the reason you could not prove the correctness of the reduction is, that the reduction as given is not correct. (And I'm somewhat embarrassed that I only noticed this after your followup question in the comment.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/26362