News for hackers. Stuff that matters.
Re:Solving the minimum cut problem for undirected graphs by vecter on Wednesday April 17, 2024 @12:22PM (#40066847)
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

There are no comments on this comment yet.