So I have a graph with vertices that are connected by edges. The min cut function calculates the minimum number of edges which allows the graph to be separated into two connected subgraphs. So the problem I have is that the min cut function does not give me a balanced cut, i.e. the graph is divided into two: a subgraph and a vertex, and the worst case of my problem is when the vertex appears in the decomposition of the graph. Any solution ?
1 Answers
Many graphs have many different "minimum cuts" when a minimum cut is defined as one that creates two components with the deletion of the minimum number of edges. It will often be the case that many of the these simply cut off one node from all the rest since this can usually be done with a single edge deletion.
So, you need to modify your algorithm so that it keeps searching through the available minimum cuts until one is found that meets your 'balanced' criterium.
Consider this graph
There are 6 different minimum cuts ( size 3 ) that give a single isolated node. One is
An un-modified algorithm will probably find one of these and quit.
You need to keep going until you find one like this
Since your question does not specify the algorithm you use, it is not possible to give concrete advice. FYI here ( https://github.com/JamesBremner/PathFinder3/blob/main/src/Karger.cpp ) is some C++ code implementing the Karger algorithm ( https://en.wikipedia.org/wiki/Karger%27s_algorithm ) with an option to return a minimum cut that has the best balance of node numbers in each component
Related