most recent 30 from http://mathoverflow.net 2013-05-19T01:39:56Z http://mathoverflow.net/feeds/question/8379 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/8379/min-cut-and-max-cut foo bar 2009-12-09T18:12:48Z 2009-12-10T17:37:03Z

<p>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?</p>

http://mathoverflow.net/questions/8379/min-cut-and-max-cut/8382#8382 Harald Hanche-Olsen 2009-12-09T18:47:15Z 2009-12-09T18:47:15Z

<p>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.</p>

http://mathoverflow.net/questions/8379/min-cut-and-max-cut/8383#8383 S. Carnahan 2009-12-09T18:50:48Z 2009-12-10T00:25:28Z

<p>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.</p> <p><b>Edit:</b> A previous version complained about a difference in input type, hence David's comment.</p>

http://mathoverflow.net/questions/8379/min-cut-and-max-cut/8464#8464 Suresh Venkat 2009-12-10T17:37:03Z 2009-12-10T17:37:03Z

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