TY - GEN
T1 - Generating cut conjunctions and bridge avoiding extensions in graphs
AU - Khachiyan, L.
AU - Boros, E.
AU - Borys, K.
AU - Elbassioni, K.
AU - Gurvich, V.
AU - Makino, K.
PY - 2005
Y1 - 2005
N2 - Let G = (V, E) be an undirected graph, and let B ⊆ V × V be a collection of vertex pairs. We give an incremental polynomial time algorithm to enumerate all minimal edge sets X ⊆ E such that every vertex pair (s, t) ∈ B is disconnected in (V, E \ X), generalizing well-known efficient algorithms for enumerating all minimal s-t cuts, for a given pair s, t ∈ V of vertices. We also present an incremental polynomial time algorithm for enumerating all minimal subsets X ⊆ E such that no (s, t) ⊆ B is a bridge in (V, X ∪ 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 ∪ B, enumerate all minimal subsets X ⊆ E such that no element b ∈ B is spanned by E \ X. Unlike the above special cases, corresponding to the cycle and cocycle matroids of the graph (V, E ∪ B), the enumeration of cut conjunctions for vectorial matroids turns out to be NP-hard.
AB - Let G = (V, E) be an undirected graph, and let B ⊆ V × V be a collection of vertex pairs. We give an incremental polynomial time algorithm to enumerate all minimal edge sets X ⊆ E such that every vertex pair (s, t) ∈ B is disconnected in (V, E \ X), generalizing well-known efficient algorithms for enumerating all minimal s-t cuts, for a given pair s, t ∈ V of vertices. We also present an incremental polynomial time algorithm for enumerating all minimal subsets X ⊆ E such that no (s, t) ⊆ B is a bridge in (V, X ∪ 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 ∪ B, enumerate all minimal subsets X ⊆ E such that no element b ∈ B is spanned by E \ X. Unlike the above special cases, corresponding to the cycle and cocycle matroids of the graph (V, E ∪ B), the enumeration of cut conjunctions for vectorial matroids turns out to be NP-hard.
UR - http://www.scopus.com/inward/record.url?scp=33744958130&partnerID=8YFLogxK
U2 - 10.1007/11602613_17
DO - 10.1007/11602613_17
M3 - Conference contribution
AN - SCOPUS:33744958130
SN - 3540309357
SN - 9783540309352
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 156
EP - 165
BT - Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings
T2 - 16th International Symposium on Algorithms and Computation, ISAAC 2005
Y2 - 19 December 2005 through 21 December 2005
ER -