David Eppstein shows [a variant of max-cut problem is NP-hard][1], which is asked by Aaron.


  [1]: http://cstheory.stackexchange.com/questions/3690/a-multi-cut-problem/3695#3695