6 ms·

Solving the minimum cut problem for undirected graphs

214 points by Anon84 3y ago

JohnKemeny 3y ago
If you settle for randomized, Karger's algorithm is amazing. https://en.m.wikipedia.org/wiki/Karger%27s_algorithm https://en.m.wikipedia.org/wiki/Karger%27s_algorithm
- NooneAtAll3 3y ago
  I wonder why wikipedia still hasn't implemented transfer of pc users back away from mobile version...
  - paxys 3y ago
    Why would they? Plenty of PC users prefer the m.wikipedia.org layout, even on desktop.
    - interroboink 3y ago
      I know some mobile users prefer the PC layout — but surely it would be a legitimate complaint if Wikipedia started redirecting in that direction, instead? I think the point is: there are different sites intended for different devices, and you should get the one that matches yours (with a reasonable way to override it, of course).
    - NooneAtAll3 3y ago
      because it does redirect mobile users there obviously it should do the same in the other direction
- sltkr 3y ago
  The problem with Karger's algorithm isn't that it's randomized, but that even the expected runtime is orders of magnitude worse than this new deterministic algorithm. For that reason I wouldn't call it amazing though it is an interesting algorithm.
VHRanger 3y ago
I don't understand how their min cut preserving sparsification works. You sample edges, and it's supposed to always happen to include the relevant min cut edges? How?
- vecter 3y ago
  My very rough understanding from reading the article (I could be wrong, I'm not a researcher) is that this is accomplished by the key insight of Kawayabarashi and Thorup (2015), which is that min-cuts must have low conductance. So it seems that you can partition the graph into well-connected components (perhaps by measuring the conductance of edges?) and preserve the min-cut of the original graph in the new reduced graph where you contract each the partitioned components into a single node. Unless you're asking about the randomized graph sparsification of Benzur and Karger, in which case the output is correct with high probability [0], but like with many randomized algorithms, is not guaranteed to be correct. [0] https://en.wikipedia.org/wiki/With_high_probability https://en.wikipedia.org/wiki/With_high_probability
- teraflop 3y ago
  The details of the paper are way over my head, but here's what I took away from a quick skim. The random sampling technique of Benzur and Karger approximately preserves the total weights of all cuts in the graph, up to certain error bounds (with high probability). That is, if you draw a particular cut through the graph, the original version might have 100 edges crossing the cut, and the sparse graph might have 3 edges crossing the cut with a total weight of 102. Since all cut sizes are approximately preserved, you can get an approximate answer to the min cut in the original graph by solving the same problem on the sparse graph. The deterministic, exact approach is a lot more complicated. In this case, we're not trying to preserve all cut weights, just the weights of minimum cuts. If you imagine a graph that consists of some dense "clusters" connected by other sparse "bottlenecks", then a minimum cut must go through the bottlenecks while avoiding the clusters. So hand-waving the details, if you could exactly partition the graph into dense clusters, you could just collapse each cluster into a single vertex, and then easily solve the min-cut problem on the graph of clusters instead of the original graph. This partitioning is hard to do exactly. But if you start by doing it approximately, then you can bound the number of "adjustments" that need to be made in order to make the partitioning work.
regularfry 3y ago
For a use case, graph cutting was one of the original techniques behind seam carving: https://en.wikipedia.org/wiki/Seam_carving https://en.wikipedia.org/wiki/Seam_carving
- ygra 3y ago
  We've implemented making space in a graph drawing a few years ago where a user would basically say that they want some free space somewhere in an existing drawing and everything else should shift in a way to clear that space, but also to not destroy the drawing too much. One approach I thought about was basically seam carving (apparently coming full circle here), the "global" strategy here: http://live.yworks.com/demos/layout/clearrectanglearea/ http://live.yworks.com/demos/layout/clearrectanglearea/ ... although sadly it happened to not work out that well in practice and we found better ways of handling that.
cyberbender 3y ago
Wow, I remember attempting to do this in University...glad someone much smarter than me figured it out :)
dontreact 3y ago
Could this be used for maximum cut? Maximum cut at one point was an important concept in IIT which is a somewhat debunked but still interesting theory of consciousness
- Tryk 3y ago
  Invert all edge weights.
  - fuglede_ 3y ago
    This would prove P = NP. The catch being that only positive weights are allowed.
    - deleted 3y ago
      [deleted]
- CountHackulus 3y ago
  I remember learning an amazing randomized algorithm for max cut. If you pick edges at random 50/50 to be cut, you get a 2-approximation to the optimal solution. That is it's no more than twice as bad. Really not bad for "just guess".
  - karmakurtisaani 3y ago
    The first approximation algorithm, invented by Erdős. The best known by Goemans and Williamson achieves about 0.868 (IIRC) approximation, and is a thing of beauty as well.
    - akoboldfrying 3y ago
      A rare example of a constant-factor approximation algorithm with a constant that's... actually useful in practice.
- anticensor 3y ago
mijoharas 3y ago
This proof is interesting, and the article is also great in explaining what it's doing, and how. Is there any link to how the algorithm actually works, rather than why? (i.e. can I see some code somewhere). I read the article, and skimmed the paper, but didn't immediately see it. ok, I went back and reskimmed the paper, turns out "algorithm A1" is in the appendices, I guess that's it? I haven't dug into it much yet. Can anyone confirm? (And can anyone link to an equivalent written in an actual programming language, which I'd find easier to parse)
adverbly 3y ago
I wonder if this was at all inspired by question 25 of the latest Advent of code.
- vecter 3y ago
  I doubt it. Finding faster deterministic min-cut algorithms has been an interesting problem for a long time. Programming puzzles have no practical impact on theoretical research.
- deleted 3y ago
  [deleted]
ryandv 3y ago
The min-cut problem was in fact the last problem for Advent of Code 2023 [0]. Many algorithms were too big-brained for me, but I was able to find "A Simple Min-Cut Algorithm" [1] which was relatively easy to understand. It uses maximum adjacency search [2] to traverse the graph in descending order of the number of incident edges from each vertex to all previously visited vertices, possibly factoring in their weights; the last two visited vertices are then merged, and the cut separating the last vertex visited from the rest of the graph is stored. The process repeats until all but two vertices have been merged; the smallest cut found in each iteration, by sum of weights of edges that need to be severed to separate the last vertex from the rest of the graph, induces a min-cut for the entire graph; since vertices have been merged together you will need to map from edges incident to the merged vertex back to edges incident to all vertices "contained" in that merged vertex. The advantage of implementing maximum adjacency search is that it can also be used to traverse and count components of the resulting cut graph to verify it has indeed been partitioned in two. Something like that anyway. It's been a little while. [0] https://adventofcode.com/2023/day/25 https://adventofcode.com/2023/day/25 [1] https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/stoerwagner-mincut.pdf https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handou... [2] https://dl.acm.org/doi/pdf/10.5555/313559.313872 https://dl.acm.org/doi/pdf/10.5555/313559.313872
- d0mine 3y ago
  Here's solution using networkx Python module: cutset = nx.minimum_edge_cut(G) for e in cutset: G.remove_edge(*e) size1, size2 = map(len, nx.connected_components(G)) answer = size1 * size2
  - ryandv 3y ago
    Elegant. For whatever reason I elected to roll my own graph implementation in my own solution, with predictably terrible performance characteristics: using adjacency lists (instead of matrices) and BTreeSets to model "merged" vertices was not the greatest idea in hindsight.. At least it spit out the right answer after a while.
  - guiambros 3y ago
John_da 3y ago
[dead]
mehulashah 3y ago
I remember implementing Karger’s algorithm in Cilk back in 1997. Wanted to parallelize it on an SMP. It’s great to see the deterministic version discovered and published.

214 points by Anon84 3y ago

If you settle for randomized, Karger's algorithm is amazing. https://en.m.wikipedia.org/wiki/Karger%27s_algorithm https://en.m.wikipedia.org/wiki/Karger%27s_algorithm

NooneAtAll3 3y ago
I wonder why wikipedia still hasn't implemented transfer of pc users back away from mobile version...
- paxys 3y ago
  Why would they? Plenty of PC users prefer the m.wikipedia.org layout, even on desktop.
  - interroboink 3y ago
    I know some mobile users prefer the PC layout — but surely it would be a legitimate complaint if Wikipedia started redirecting in that direction, instead? I think the point is: there are different sites intended for different devices, and you should get the one that matches yours (with a reasonable way to override it, of course).
  - NooneAtAll3 3y ago
    because it does redirect mobile users there obviously it should do the same in the other direction
sltkr 3y ago
The problem with Karger's algorithm isn't that it's randomized, but that even the expected runtime is orders of magnitude worse than this new deterministic algorithm. For that reason I wouldn't call it amazing though it is an interesting algorithm.

VHRanger 3y ago

I don't understand how their min cut preserving sparsification works. You sample edges, and it's supposed to always happen to include the relevant min cut edges? How?

vecter 3y ago
My very rough understanding from reading the article (I could be wrong, I'm not a researcher) is that this is accomplished by the key insight of Kawayabarashi and Thorup (2015), which is that min-cuts must have low conductance. So it seems that you can partition the graph into well-connected components (perhaps by measuring the conductance of edges?) and preserve the min-cut of the original graph in the new reduced graph where you contract each the partitioned components into a single node. Unless you're asking about the randomized graph sparsification of Benzur and Karger, in which case the output is correct with high probability [0], but like with many randomized algorithms, is not guaranteed to be correct. [0] https://en.wikipedia.org/wiki/With_high_probability https://en.wikipedia.org/wiki/With_high_probability
teraflop 3y ago
The details of the paper are way over my head, but here's what I took away from a quick skim. The random sampling technique of Benzur and Karger approximately preserves the total weights of all cuts in the graph, up to certain error bounds (with high probability). That is, if you draw a particular cut through the graph, the original version might have 100 edges crossing the cut, and the sparse graph might have 3 edges crossing the cut with a total weight of 102. Since all cut sizes are approximately preserved, you can get an approximate answer to the min cut in the original graph by solving the same problem on the sparse graph. The deterministic, exact approach is a lot more complicated. In this case, we're not trying to preserve all cut weights, just the weights of minimum cuts. If you imagine a graph that consists of some dense "clusters" connected by other sparse "bottlenecks", then a minimum cut must go through the bottlenecks while avoiding the clusters. So hand-waving the details, if you could exactly partition the graph into dense clusters, you could just collapse each cluster into a single vertex, and then easily solve the min-cut problem on the graph of clusters instead of the original graph. This partitioning is hard to do exactly. But if you start by doing it approximately, then you can bound the number of "adjustments" that need to be made in order to make the partitioning work.

regularfry 3y ago

For a use case, graph cutting was one of the original techniques behind seam carving: https://en.wikipedia.org/wiki/Seam_carving https://en.wikipedia.org/wiki/Seam_carving

ygra 3y ago
We've implemented making space in a graph drawing a few years ago where a user would basically say that they want some free space somewhere in an existing drawing and everything else should shift in a way to clear that space, but also to not destroy the drawing too much. One approach I thought about was basically seam carving (apparently coming full circle here), the "global" strategy here: http://live.yworks.com/demos/layout/clearrectanglearea/ http://live.yworks.com/demos/layout/clearrectanglearea/ ... although sadly it happened to not work out that well in practice and we found better ways of handling that.

cyberbender 3y ago

Wow, I remember attempting to do this in University...glad someone much smarter than me figured it out :)

dontreact 3y ago

Could this be used for maximum cut? Maximum cut at one point was an important concept in IIT which is a somewhat debunked but still interesting theory of consciousness

Tryk 3y ago
Invert all edge weights.
- fuglede_ 3y ago
  This would prove P = NP. The catch being that only positive weights are allowed.
  - deleted 3y ago
    [deleted]
CountHackulus 3y ago
I remember learning an amazing randomized algorithm for max cut. If you pick edges at random 50/50 to be cut, you get a 2-approximation to the optimal solution. That is it's no more than twice as bad. Really not bad for "just guess".
- karmakurtisaani 3y ago
  The first approximation algorithm, invented by Erdős. The best known by Goemans and Williamson achieves about 0.868 (IIRC) approximation, and is a thing of beauty as well.
  - akoboldfrying 3y ago
    A rare example of a constant-factor approximation algorithm with a constant that's... actually useful in practice.
anticensor 3y ago

mijoharas 3y ago

This proof is interesting, and the article is also great in explaining what it's doing, and how. Is there any link to how the algorithm actually works, rather than why? (i.e. can I see some code somewhere). I read the article, and skimmed the paper, but didn't immediately see it. ok, I went back and reskimmed the paper, turns out "algorithm A1" is in the appendices, I guess that's it? I haven't dug into it much yet. Can anyone confirm? (And can anyone link to an equivalent written in an actual programming language, which I'd find easier to parse)

adverbly 3y ago

I wonder if this was at all inspired by question 25 of the latest Advent of code.

vecter 3y ago
I doubt it. Finding faster deterministic min-cut algorithms has been an interesting problem for a long time. Programming puzzles have no practical impact on theoretical research.
deleted 3y ago
[deleted]

ryandv 3y ago

The min-cut problem was in fact the last problem for Advent of Code 2023 [0]. Many algorithms were too big-brained for me, but I was able to find "A Simple Min-Cut Algorithm" [1] which was relatively easy to understand. It uses maximum adjacency search [2] to traverse the graph in descending order of the number of incident edges from each vertex to all previously visited vertices, possibly factoring in their weights; the last two visited vertices are then merged, and the cut separating the last vertex visited from the rest of the graph is stored. The process repeats until all but two vertices have been merged; the smallest cut found in each iteration, by sum of weights of edges that need to be severed to separate the last vertex from the rest of the graph, induces a min-cut for the entire graph; since vertices have been merged together you will need to map from edges incident to the merged vertex back to edges incident to all vertices "contained" in that merged vertex. The advantage of implementing maximum adjacency search is that it can also be used to traverse and count components of the resulting cut graph to verify it has indeed been partitioned in two. Something like that anyway. It's been a little while. [0] https://adventofcode.com/2023/day/25 https://adventofcode.com/2023/day/25 [1] https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/stoerwagner-mincut.pdf https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handou... [2] https://dl.acm.org/doi/pdf/10.5555/313559.313872 https://dl.acm.org/doi/pdf/10.5555/313559.313872

d0mine 3y ago
Here's solution using networkx Python module: cutset = nx.minimum_edge_cut(G) for e in cutset: G.remove_edge(*e) size1, size2 = map(len, nx.connected_components(G)) answer = size1 * size2
- ryandv 3y ago
  Elegant. For whatever reason I elected to roll my own graph implementation in my own solution, with predictably terrible performance characteristics: using adjacency lists (instead of matrices) and BTreeSets to model "merged" vertices was not the greatest idea in hindsight.. At least it spit out the right answer after a while.
- guiambros 3y ago

John_da 3y ago

[dead]

mehulashah 3y ago

I remember implementing Karger’s algorithm in Cilk back in 1997. Wanted to parallelize it on an SMP. It’s great to see the deterministic version discovered and published.