Unless I misread your question, your problem is identical to maximum cut when $G'=G$, implying your problem is NP-hard.
Dustin G. Mixon
- 7.6k
- 2
- 31
- 56