 An extension of Karger’s algorithm due to David Karger and Clifford Stein achieves an order of magnitude improvement.The basic idea is to perform the contraction procedure until the graph reaches formula_33 vertices.The probability formula_40 that this contraction procedure avoids a specific cut formula_23 in an formula_22-vertex graph is
formula_43

This expression is approximately formula_44 and becomes less than formula_45 around formula_46.