News for hackers. Stuff that matters.
Re:Runtime improvement for Minimum Cut algorithm first time ... by londons_explore on Monday January 11, 2021 @06:54AM (#25727749)
Can someone give a more concrete example of this problem?

I read the wiki page[1], and I'm left with the impression that for almost all cases, the minimum cut will be to pick a node and seperate it from the rest of the nodes. It doesn't sound like a very computationally difficult or useful algorithm if one of the two parts of the results usually consists of a single node...

[1]: https://en.wikipedia.org/wiki/Minimum_cut

Re:Runtime improvement for Minimum Cut algorithm first time ... by est31 on Monday January 11, 2021 @07:50AM (#25728207)
The classical example used to introduce this problem in lectures is the one about the soviet rail network: https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-ma...

Legend has it both Soviets and Americans studied it, both identifying the bottleneck for opposite reasons: Americans wanted to disrupt as much as possible by destroying as few rails as possible while Soviets wanted to extend the network's ability to transport goods with building the fewest connections... Both problems are equivalent, known as the max flow min cut theorem.

Re:Runtime improvement for Minimum Cut algorithm first time ... by interpol_p on Monday January 11, 2021 @07:23AM (#25727964)
I used the minimum cut algorithm to implement a texture synthesis algorithm [1]. When the images to merge are represented as a graph of connected pixels, you can use the minimum cut algorithm to try to find the lowest energy path that cuts across both images

This minimises the differences between the images along the seam so they appear to blend together

[1] https://www.cc.gatech.edu/~turk/my_papers/graph_cuts.pdf

Re:Runtime improvement for Minimum Cut algorithm first time ... by xdavidliu on Monday January 11, 2021 @07:59AM (#25728287)
> for almost all cases, the minimum cut will be to pick a node and seperate it from the rest of the nodes.

You're assuming that nodes have 1 or 2 edges coming out of them. If every node has up to (# nodes)-1 edges incident on it, then it's non-obvious which of the 2^(# node) subsets gives the min cut.

It's definitely not justified to only consider the subsets with 1 nodes: what if you have 10 nodes: 5 blue and 5 yellow, and the blue ones are all connected to each other with extremely heavy edges, and similar for the yellow nodes, and there is one very light edge between the two regions? Then in this case, the min cut would be to separate blue from yellow (i.e. cut off a 5-node subset), _not_ 1 node.

The general case of arbitrary nodes and edges will be somewhere in between what I have described and what you're thinking of, so a general algorithm that works for all cases is definitely not as trivial as just trying out every 1-node subset.

Re:Runtime improvement for Minimum Cut algorithm first time ... by ivanbakel on Monday January 11, 2021 @07:45AM (#25728163)
Wikipedia has a nice diagram on another page[0] - in a weighted graph where all nodes have enough connections, separating just a single node is likely to cost more than finding some cheap partition between two groups.

[0] https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm...

Re:Runtime improvement for Minimum Cut algorithm first time ... by wdevanny on Monday January 11, 2021 @12:11PM (#25731986)
Repeating a concrete example from another comment:

> Take two copies of K_4. Connect them with a single edge. The minimum cut is the single connector edge while your proposed strategy would delete the three edges out of one of the vertices not incident to the connector edge.