Maximize graph with k cut edge operations I have undirected graph with N nodes each with some weight. There are M edges and in exactly K operations I want to maximize the XOR sum of connected components of the graph. ((n1 XOR n2 XOR n3) + (c1 XOR c2 XOR c3)).
(There can be multiple edges between 2 nodes.

I've tried attempting it with Minimum spanning tree with cut edge but couldn't succeed. Any help?
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.