To the best of my knowledge, the best algorithm for the minimum s-t cut in a weighted digraph is the Goldberg push-relabel algorithm with $O(n^{2}\sqrt{m})$ time complexity. I'm interested in solving this problem as a separation sub-problem inside a branch and cut algorithm, so I don't always need the optimal solution. Is there a heuristic/approximation/randomized algorithm for the min s-t cut problem with better time complexity?


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.