<p>I guess this problem is NP-hard.</p>

<p>It is known that finding the minimum k-cut that separates k specified vertices is NP-hard (<a href="https://en.wikipedia.org/wiki/Minimum_k-cut" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Minimum_k-cut</a>). 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.</p>

CC BY-SA 3.0
2018-02-04T08:55:20.143Z
2018-02-04T08:55:20.143Z
tianyiz
<p>I have undirected graph with <strong>N</strong> nodes each with <strong>some weight</strong>. There are <strong>M</strong> edges and in <strong>exactly K</strong> 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.</p>

<p>I've tried attempting it with Minimum spanning tree with cut edge but couldn't succeed. Any help?</p>

<graph-theory><graph-algorithms><np-complete>
Maximize graph with k cut edge operations
Neha
# Maximize graph with k cut edge operations

(Asked by: username_0 on 2018-02-04)

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?

**Tags:** graph-theory, graph-algorithms, np-complete

---

## 1 answers

### Answer by username_1 on 2018-02-04. Score: 1

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.


---

