When \(G\)  is a general graph, there is an \(O(\log n\) )-approximation
algorithm [1]}, [2]} via the equivalence to
Undirected Multicut, which is hard to approximate within any
constant factor assuming the Unique Games Conjecture
(UGC) [3]}. For the maximization version where the goal is
to maximize the number of \(+\) edges within the same cluster plus the
number of \(-\) edges between different clusters, Charikar, Guruswami,
and Wirth [1]} and Swamy [5]} gave
\(0.766\) -approximation algorithms based on rounding semidefinite
programs.
