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