DIMACS TR: 2005-24

Enumerating Cut Conjunctions in Graphs and Related Problems

Authors: Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich and Kazuhisa Makino


Let G = (V,E) be an undirected graph, and let $B \subseteq V \times V$ be a collection of vertex pairs. We give an incremental polynomial time algorithm to enumerate all minimal edge sets $X \subseteq E$ such that every vertex pair $(s,t) \in B$ is disconnected in $(V,E\setminus X)$, generalizing well-known efficient algorithms for enumerating all minimal s-t cuts, for a given pair $s, t \in V$ of vertices. We also present an incremental polynomial time algorithm for enumerating all minimal subsets $X \subseteq E$ such that no $(s, t) \in B$ is a bridge in $(V,X \bigcup B)$. These two enumeration problems are special cases of the more general cut conjunction problem in matroids: given a matroid M on ground set $S = E \bigcup B$, enumerate all minimal subsets $X \subseteq E$ such that no element $b \in B$ is spanned by $E \setminus X$. Unlike the above special cases, corresponding to the cycle and cocycle matroids of the graph $(V,E \bigcup B)$, the enumeration of cut conjunctions for vectorial matroids turns out to be NP-Hard.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-24.pdf
DIMACS Home Page