Generating cut conjunctions in graphs and related problems
Let G=(V,E) be an undirected graph, and let B (subset of) under barV x V be a collection of vertex pairs. We give an incremental polynomial time algorithm to generate all minimal edge sets X (subset of) under bar E such that every pair (s,t) is an element of B of vertices is disconnected in (V, E backslash X), generalizing well-known efficient algorithms for generating all minimal s-t cuts, for a given pair s,t of vertices. We also present an incremental polynomial time algorithm for generating all minimal subsets X (subset of) under bar E such that no (s,t) is an element of B is a bridge in (V, X boolean OR B). Both above problems are special cases of a more general problem that we call generating cut conjunctions for matroids: given a matroid M on ground set S=E boolean OR B, generate all minimal subsets X (subset of) under bar E such that no element b is an element of B is spanned by E backslash X. Unlike the above special cases, corresponding to the cycle and cocycle matroids of the graph (V, E boolean OR B), the more general problem of generating cut conjunctions for vectorial matroids turns out to be NP-hard.
cut conjunction graph matroid cut generation multicut