P495: Enumeration of all minimal cut-disjunctions of an undirected graph.

P495: Enumeration of all minimal cut-disjunctions of an undirected graph.

Input:

An undirected graph $G=(V, E)$ and $\mathcal{P} = \{(s_i, t_i ) \in V \times V \mid i \in [k] \}$.

Output:

All minimal cut-disjunctions of $G$.

Complexity:

Incremental polynomial time.

Comment:

A minimal cut-disjunction is a minimal set of edges $E'$ such that some pair of vertices in $\mathcal{P}$ is disconnected in $(V, E\setminus E')$.

Reference:

[Khachiyan2007] (Bibtex)