Unless I misread your question, your problem is identical to [maximum cut][1] when $G'=G$, implying your problem is NP-hard.

  [1]: http://en.wikipedia.org/wiki/Maximum_cut