Reduction from max-cut to min-cut

Algorithms for the finding of an MST in a graph can be applied for both maximum and minimum spanning trees.

It is well known, however, that the finding of a max-cut in a graph is an NP-hard problem while the min-cut problem can be easily solved in polynomial time.

Why aren't the two equivalent?

What is the restriction that I’m missing here?

Thanks!

Some intuition involves the notion of a convex function. You can look up the formal definition, or consider the quintessential example of a convex function, namely $x^2$. Minimizing a convex function is easy, since there is a unique minimum, and moreover if you start anywhere and keep going done, you will eventually reach the minimum. Maximizing a convex function is a different thing. Suppose for example that you want to maximize $x^2$ under the constraint $x \in [\alpha,\beta]$. In order to do that, you need to compute the function at both endpoints $\alpha,\beta$ and choose the maximum. Now imagine that you function is multivariate and has lots of inputs. Minimizing is still easy - there is a unique minimum that can be reached by descent - but maximizing is problematic, since there are many potential maxima.

MAX-CUT and MIN-CUT are related to the cut function, which gets as input a cut, and outputs the number of edges cut. This is a set function rather than a function on $\mathbb{R}^n$, but it has the property of submodularity, which is a form of convexity for set functions. Indeed, in general one can minimize submodular functions, but maximizing them is NP-hard.

StackExchange Computer Science Q#19263, answer score: 3