Random Deletion for Circuits in Regular MatroidsResearch Paper
Karger's random contraction algorithm ([Kar93], [Kar95]) showed that a graph with minimum cut weight has at most cuts of weight at most . Through matroid duality, cuts of a graph are the circuits of its cographic matroid and cycles are the circuits of its graphic matroid, and Subramanian ([Sub95]) proved the analogous bound …