Maximize graph with k cut edge operations
I guess this problem is NP-hard.

It is known that finding the minimum k-cut that separates k specified vertices is NP-hard (https://en.wikipedia.org/wiki/Minimum_k-cut). Therefore, given a minimum k-cut instance as well as k specified vertices, we can assign weight-1 to all the k specified vertices, and weight-0 to other vertices. Finally we apply the blackbox algorithm for your XOR problem to binary-search for the minimum k-cut size.