András Benczúr, Otilia Fülöp, ESA 2000

Fast algorithms for even/odd mincuts and generalizations

by András A. Benczúr and Otília Fülöp,

Proc. European Symp. Alg., Springer Lecture Notes in Computer Science 1879, pp. 88-99 (2000)

Abstract

We give algorithms for the directed minimum odd or even cut problem and certain generalizations. Our algorithms improve on the previous best ones of Goemans and Ramakrishnan by a factor of O(n) (here n is the size of the ground vertex set). Our improvements apply among others to the minimum directed T-odd or T-even cut and to the directed minimum Steiner cut problems. The (slightly more general) result of Goemans and Ramakrishnan shows that a collection of minimal minimizers of a submodular function (i.e. minimum cuts) contains the odd minimizers. In contrast our algorithm selects an n-times smaller class of not necessarily minimal minimizers and out of these sets we construct the odd minimizer. If M (n, m) denotes the time of a u-v minimum cut computation in a directed graph with n vertices and m edges, then we may find a directed minimum

odd or T-odd cut with V (or T) even in O (n^2 m + n M (n, m)) time;
even or T-even cut in O (n^3 m + n^2 M (n, m)) time.

The key of our construction is a so-called parity uncrossing step that, given an arbitrary set system with odd intersection, finds an odd set with value not more than the maximum of the initial system.

Related Papers

Michel X. Goemans and V.S. Ramakrishnan
Minimizing Submodular Functions over Families of Sets
Combinatorica, 15, 499--513, 1995.