Question

A cut in an undirected graph is a separation of the vertices V into two disjoint subsets S and T . The size of a cut is the number of edges that have one endpoint in S and the other in T . Let $\mathbf{MAX}-\mathbf{CUT}=\left\{<\mathbf{G},\mathbf{K}>|\mathbf{G}\mathbf{has}\mathbf{a}\mathbf{cut}\mathbf{of}\mathbf{size}\mathbf{k}\mathbf{or}\mathbf{more}\right\}.$

Show that MAX-CUT is NP-complete. You may assume the result of Problem 7.26. (Hint: Show that$\ne \mathbf{SAT}⩽\mathbf{P}\mathbf{MAX}\mathbf{CUT}$. The variable gadget for variable x is a collection of 3c nodes labeled with x and another nodes labeled with x . The clause gadget is a triangle of three edges connecting three nodes labeled with the literals appearing in the clause. Do not use the same node in more than one clause gadget. Prove that this reduction works.)

Short answer

$MAX-CUT$is NP-complete.

Step-by-step solution

Step 1:To find equality in the SAT

MAX-CUT is in NP. We can guess the partition of the graph into two parts and verify that the number of edges cut is at least $k$

Let $n$be the number of variables and$c$ be the number of clauses in the $\ne$S A T.

Boolean comparison on the number

For forward direction,

assume that$a\ne -$ assignment

Place all nodes labeled by a TRUE literal on one side of the cut and all nodes labeled by a FALSE literal on the other side of the cut.

Also Since every clause gets a TRUE and a FALSE literal, for every triangle. Two of the three edges are cut.

For the backward direction,

Proof for any partition that cuts at least edges $k$must

Place every block on one side of the partition entirely.

Place blocks corresponding to complementary literals on opposite sides.

Therefore the partition defines an assignment to literals.

And then every clause must have a TRUE as well as a FALSE literal. So, two edges in that clause triangle getcut.