Solving the minimum cut problem for undirected graphs | Hacker News Reader

Solving the minimum cut problem for undirected graphs

research.google

214 pointsAnon8436 comments

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

[1] https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handou...

[2] https://dl.acm.org/doi/pdf/10.5555/313559.313872

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

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.

Same! I felt it'd be above my IQ-level, so networkx-ed it.

Here's another obvious solution:

    pos = nx.spring_layout(G)
    nx.draw_networkx_nodes(G, pos)
    nx.draw_networkx_edges(G, pos)
    nx.draw_networkx_labels(G, pos, font_size=10, font_color="white")
    plt.show()

Thankfully it was my fastest solution (after day 1). After 25 days, I wasn't in the mood of spending hours post-xmas dinner solving convoluted riddles.

Sorry if I am missing something, but why not run max-flow? Max-flow is simple to implement; basically just DFS/BFS in a loop. Also, a more advanced variant with better runtime, scaling max-flow, is not too much harder.

https://cseweb.ucsd.edu/classes/sp11/cse202-a/lecture8-final...

Unless I'm missing something (which is entirely possible, I have a cold and might not be thinking straight) ...

Max-Flow runs on directed graphs. These are undirected graphs.

Also, the problem is to find a global min-cut, which requires all-pairs max flow.

Not actually all-pairs max flow, you can fix the source and consider all possible sinks. In the AoC problem we also know that the min-cut is 3, so we can abort the flow algorithm as soon as we have found a 4-flow.

You can compute the max-flow of an undirected graph. The edges have capacities and in the undirected case you assume that capacity can be used in both 'directions'.

Since the AoC specifies the min-cut for you I found it was simpler to take advantage of that.

I picked two random vertices and found the shortest path between them 3 times, cutting each vertex after each iteration. If after doing that I couldn't find a path between the two vertices then I had successfully partitioned the graph in two. Otherwise that meant I picked two vertices in the same partition and I reset the graph and randomly picked a different vertex.

Ended up being very quick to run, and easy to implement.

I visualized the AoC graph with graphviz and identified the minimum cut using good ol' mark 1 eyeball. Humans have an incredibly efficient algorithm for identifying "this blob is only connected to that blob with these two lines"

Just FYI, it was possible to solve Advent of Code 2023 - Day 25 using a cool Linear Algebra trick as well.

"Fiedler vector"[1] - Algebraic connectivity (without networkx): https://www.reddit.com/r/adventofcode/comments/18qbsxs/comme...

I also used networkx during the contest to solve and visualize[2] but it was good to learn the Linear Algebra approach also afterwards from the Reddit solution thread.

[1] https://en.wikipedia.org/wiki/Algebraic_connectivity?useskin... [2] https://github.com/vismit2000/compCode-II/blob/master/Advent...

If you settle for randomized, Karger's algorithm is amazing.

https://en.m.wikipedia.org/wiki/Karger%27s_algorithm

I wonder why wikipedia still hasn't implemented transfer of pc users back away from mobile version...

Why would they? Plenty of PC users prefer the m.wikipedia.org layout, even on desktop.

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).

because it does redirect mobile users there

obviously it should do the same in the other direction

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.

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

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/ ... although sadly it happened to not work out that well in practice and we found better ways of handling that.

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

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)

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

Invert all edge weights.

This would prove P = NP. The catch being that only positive weights are allowed.

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".

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.

A rare example of a constant-factor approximation algorithm with a constant that's... actually useful in practice.

No, maximum cut is a significantly harder problem. Minimum cut, on the other hand, is equivalent to maximum flow: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

No -- as another commenter pointed out, max-cut is (almost certainly) a much harder problem.

Specifically, there are algorithms that guarantee to solve every min-cut problem instance in time polynomial in the size of the problem (CS theorists call such algorithms "efficient"), while max-cut is an NP-complete problem. All NP-complete problems are "as hard as each other", and while no one has yet proven that they all take exponential time to solve, the brightest minds in CS have been searching for a faster algorithm for 40 years without success so far. Most people take that lack of progress as evidence that these problems really are hard.

The most famous NP-complete problem is probably the Travelling Salesman Problem. Another interesting one (because it seems like it "shouldn't be that hard") is Partition: Given a set of integers, can you partition them into two halves with equal sum?

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

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.

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.

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?

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

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.

Reply on news.ycombinator.com