Min-Cut E(S,T)={uw∈E|u∈S,v∈T} Undirected graph G(V,E) Bi-partition of Vinto nonempty S and T Find a cut E(S,T)of smallest size (global min-cut) Deterministic algorithms: max-flow min-cut(duality) best upper bound (2021):m1+(1) O(.):ignore poly-logarithmic factorsMin-Cut • Undirected graph • Bi-partition of into nonempty and • Find a cut of smallest size (global min-cut) • Deterministic algorithms: • max-flow min-cut (duality) • best upper bound (2021): G(V, E) V S T E(S, T) m1+o(1) T S E(S, T) = {uv ∈ E ∣ u ∈ S, v ∈ T} : ignore poly-logarithmic factors O˜( ⋅ )