$\begingroup$
MaxCut problem:
Given an undirected graph G(V,E), find a cut between the vertices, such that the number of edges crossing the cut is maximal.
Example:
How can I prove that this is NPC problem?
This is homework, I know I should show you what I have tried, but I have no idea how to do it. Can someone please help me, and show me "How to prove it for dummies" (I do not want to just copy and give to the teacher, I want to understand it)
$\endgroup$1 Answer
$\begingroup$The reduction is not straightforward. We need reduce from 3-sat to nae 4-sat to nae 3-sat to max cut.
$\endgroup$Reference:
