Non probabilistic algorithm for min-cut problem?

Question

I know about Karger's algorithm and its variations, all of them being probabilistic. Is there non-trivial (i.e. non-brutefoce) deterministic algorithm for mincut problem?

Answer 1

One method to solve this problem is to use the following. Let $c(S|T)$ be the cost of a cut (i.e. the total weight of the edges going from $S$ to $T$, and let $c(f)$ be the value of a flow going from $s$ to $t$.

Theorem: Let $G$ be a connected graph, and let $s,t$ be vertices of $G$. Then $$\min_{(S,T) \text{ cut}} c(S|T) = \max_{f \text{ flow from $s$ to $t$}} c(f).$$

Thus, finding a cut of minimum cost amounts to finding a flow of maximum value. The latter problem can be solved by a lot of deterministic algorithms. I would say that the Ford-Fulkerson and Edmonds-Karp algorithms are the more common.

If you want to know why the theorem above holds, you can express the min-cut problem as a linear program and use the duality theorem of linear programming.

Answer 2

Just solved the problem deterministically in near-linear time..

http://arxiv.org/abs/1411.5123