0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.