I had a question about a different randomized min cut algorithm (I don't think it is as efficient as Karger's algorithm for larger sizes of min cuts but it is more efficient for smaller ones).

My idea for an algorithm was that given some graph, I would randomly assign directions to its edges (i.e. flip a coin and if tails assign an edge to the vertex and if it's away, assign an edge from the vertex) (O(n) time). Then run Kosaraju's algorithm (O(n) time) to find all the strongly connected components. Then, we count the number of edges that are connected to each strongly connected component to find the size of the min cut. We return the smallest number and then run the algorithm more times as we do with randomized algorithms.

The intuition behind this algorithm is that I want to find different partitions of the vertices of the graph and I can do this by finding different strongly connected components if I assign directions to the graph. The only partition I cannot create is that of vertices that do not share an edge. However, there is no need to have two such vertices to be in a partition together because we can just take one or the other and have a smaller min cut.

I need help with analyzing the success rate. In a successful run of this algorithm, all of the vertices in the smaller partition of the min cut form a cycle. If the partition contains $m$ vertices and $j$ edges. Then I think the probability that it is successful is $\binom{j}{m}\frac{1}{2^{m-1}}$, since we choose $m$ of the edges to form a cycle and set them to form the cycle, but I am not really sure. If $k$ is the size of the min cut, we also need to make sure that the min cut does not point to something else, so that is another $\frac{1}{2^k}$ probability. I am not completely sure about this either, because it is very dependent on the structure of the graph and I am not sure if I am analyzing this correctly.

Any help/pointers/guidance would be appreciated. Thank you!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.