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
ABSTRACT
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