Welcome to MathOverflow

Question

0

If you want to maximize a function f(x), you can do this by minimizing -f(x). Naively it seems like an analogous trick could convert a max cut problem into a min cut problem, however this is apparently not possible because min cut is easy while max cut is hard. What is the clearest explanation of how this naive intuition goes wrong?

flag	asked Dec 9 2009 at 18:12 foo bar 1

Harald Hanche-Olsen · Answer 1 · 2009-12-09 18:47:15Z UTC

3

The ease of the minimum cut selection depends on the edge capacities being non-negative. If you negate all the capacities, that assumption goes out the window. And there is no positive edge function you can add to reinstate it.

answered Dec 9 2009 at 18:47

Harald Hanche-Olsen
5,750●1●13●34

S. Carnahan · Answer 2 · 2009-12-10 00:25:28Z UTC

If you try to take the complement of the edge set to translate a max cut problem, you end up not minimizing cuts, but cuts minus a correction factor that depends on the size of the subsets in the partition (namely, it is the product of the sizes). This changes the nature of the problem considerably - if you have a dense graph, min cut will tend to separate a small chunk, while the corrected version will not.

Edit: A previous version complained about a difference in input type, hence David's comment.

Suresh Venkat · Answer 3 · 2009-12-10 17:37:03Z UTC

1

see also: shortest path (Dijkstra/bfs) and longest path (NP-hard) in a graph

answered Dec 10 2009 at 17:37

Suresh Venkat
2,687●8●17

This analogy can be made rigorous: min cut and shortest path are dual problems in planar graphs, for which max cut and longest path are still hard. – David Eppstein Dec 10 2009 at 17:59

min cut and max cut

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.