# Heuristic algorithm for the minimum weighted s-t cut with linear running time

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?