Fully-dynamic min-cut (Q925139)

The paper is about the problem of maintaining a min-cut of a fully-dynamic (i.e. the graph may be updated by insertion and deletion of edges) graph. Its main technical contribution consists of a much more detailed analysis of a greedy tree packing technique, previously used by Karger. Namely, it is shown that in a graph with polylogarithmic edge connectivity an appropriately large greedy tree packing contains a tree crossing some min-cut only once. As the approach allows implementation in dynamic fashion, putting the results together yields the desired result -- deterministic maintenance of min-cuts of up to polylogarithmnic size and randomized maintenance of near-minimal cuts of arbitrary size.