P281: Enumeration of all cut conjunctions for a given set of vertex pairs in a graph
P281: Enumeration of all cut conjunctions for a given set of vertex pairs in a graph
Input:
A graph $G = (V,E)$, and a collection $B = \{(s_1,t_1),...,(s_k,t_k)\}$ of $k$ vertex pairs $s_i,t_i \in V$.
Output:
All cut conjunctions for $B$ in $G$.
Complexity:
Incremental polynomial time.
Comment:
A minimal edge sets $X \subseteq E$ is a \textit{cut conjunction} if, for all $i = 1, \dots, k$, vertices $s_i$ and $t_i$ is disconnected in $G' = (V, E\setminus X)$. A cut conjunction is a generalization of an $s-t$ cut.