Why is finding the maximum cut NP-hard?

Question

I recently found that finding the maximum cut in a graph with weighted edges is NP-hard. However, finding the minimum cut is not NP-hard. If I would inverse the weights on all edges and then search for the minimum cut, wouldn't that give me the maximum cut on the original graph? And if not, why?

Answer 1

I assume by inverse you mean changing a weight w to -w.

In this case, the min-cut of the adjusted graph does indeed solve the max-cut problem for the original graph.

Unfortunately, efficient algorithms for solving the min-cut problem are only known when all the weights are non-negative, which means we can only solve max-cut efficiently if all the weights are non-positive.