Could someone name a few deterministic algorithm for minimum cut of undirected graph, along with their complexity please? (By the way I learnt that there is a undirected version of Ford-Fulkerson algorithm by adding a opposing parallel edge for each directed edge, could someone tell me what is the time complexity of this one and maybe give me a bit more reference to read?)
Thanks.
Solving the global minimum cut by computing multiple maximum flows is possible but suboptimal. Using the fastest known algorithm (Orlin for sparse graphs and King-Rao-Tarjan for dense graphs), maxflow can be solved in O(mn). By picking a fixed source vertex and computing maxflow to all other vertices, we get (by the duality) the global mincut in O(mn²).
There exist several algorithms specifically for global mincuts. For algorithms independent of graph structure, the most commonly used are
Hao & Orlin's algorithm can also run very fast in practice, especially when some of the known heuristics are applied.
There are many algorithms that exploit structural properties of input graphs. I'd suggest the recent algorithm of Brinkmeier, 2007 which runs in "O(n² max(log(n), min(m/n,δ/ε))), where ε is the minimal edge weight, and δ is the minimal weighted degree". In particular, when we ignore the weights, we get O(n² log(n)) for inputs with m in o(n log(n)) and O(nm) for denser graphs, meaning its time complexity is never worse than that of N-I or S-W regardless of input.
