Max-Cut Instance:An undirected graph G(V,E). Solution:A bipartition of V into S and Ithat maximizes the cut E(S,T)={w,v}∈E|u∈S∧v∈T} .NP-hard. One of Karp's 21 NP-complete problems(reduction from the Partition problem). .a typical Max-CSP (Constraint Satisfaction Problem). Greedy is 1/2-approximate.Max-Cut Instance: An undirected graph . Solution: A bipartition of into and that maximizes the cut . G(V, E) V S T E(S, T) = {{u, v} ∈ E ∣ u ∈ S ∧ v ∈ T} T S • NP-hard. • One of Karp’s 21 NP-complete problems (reduction from the Partition problem). • a typical Max-CSP (Constraint Satisfaction Problem). • Greedy is 1/2-approximate