## Abstract

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 generate all minimal edge sets X ⊆ E such that every pair (s,t) B of vertices is disconnected in (V,E \ 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 ⊆ E such that no (s,t) B is a bridge in (V, X ∪ 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 ∪ B, generate 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 more general problem of generating cut conjunctions for vectorial matroids turns out to be NP-hard.

Original language | British English |
---|---|

Pages (from-to) | 239-263 |

Number of pages | 25 |

Journal | Algorithmica (New York) |

Volume | 51 |

Issue number | 3 |

DOIs | |

State | Published - Jul 2008 |

## Keywords

- Cut conjunction
- Cut generation
- Graph
- Matroid
- Multicut