Revision history [back]

You might have more chance by using the 'LP' algorithm that does not take care of the geometry of the graph (but we need your actual graph to check).

Another trick would be to add a very small amount of positive weight to the edges adjacent to the source and sink vertices ("very small" means that the ordering between two unequal cuts will not be modified, but the ordering between trivial cuts and other cuts with the same value will change).