Obtaining a minimum s-t cut edge set

[nowozin@…]

The boost graph library offers a set of algorithms to solve linear max-flow problems, among them push-relabel and kolmogorov max-flow algorithms.

Often, the application of the max-flow algorithm is in order to solve for a minimum edge cut set separating nodes s and t. Right now, obtaining a minimum edge cut set is not supported in the boost graph library. Thus one of the main applications of solving max flow problems is not catered for by boost graph.

Limited support for this functionality is available in the kolmogorov_max_flow algorithm by means of a color map mapping vertices to black, white and gray states. However, this is specific to the kolmogorov max flow algorithm whereas the general feature to obtain the minimum cut set is so important such that it should be an own feature supported by all max flow algorithms in the library.

Additionally, the documentation or code of the colormap in the kolmogorov max flow algorithm is wrong; there are connected but undecided states (gray) and applying the white-nonwhite or black-nonblack separation suggested in the documentation does not always yield a minimum cut set.

Thanks for considering.