2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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