Find a minimum (A, B)-vertex separator
Let $A$ and $B$ be two proper subsets of the vertex set of a graph $G$.
An (A, B)-vertex separator is a set of vertices $S$ such that, after removing $S$ from $G$, there is no path from any vertex in $A$ to any vertex in $B$. A minimum (A, B)-vertex separator is such a set $S$ with the smallest possible size. (see the concept in Menger's theorem).
In sagemath, we have vertex_cut to return a minimum vertex cut between non-adjacent vertices ๐ and ๐ก.
My problem requires an extension of this functionality.
Similarly, it is also necessary to extend edge_cut, edge_disjoint_paths(), and vertex_disjoint_paths() from two vertices to two subsets.
I would like to give some additional explanation on the comments from Max Alekseyev.
Let $G$ be a graph as shown on the left side in the following picture, and assume that $A={a,b}$ and $B={c,d}$.
Then we can check that $\{ x, y, z \}$ is the minimum (A, B)-vertex separator. If we simply add a new vertex s connected to all vertices from A, and a vertex t connected to all vertices from B, then we will get the minimum (s, t)-vertex separator $\{a,b\}$ or $\{c,d\}$, but that's not what we want.
Simply add a new vertex $s$ connected to all vertices from $A$, and a vertex $t$ connected to all vertices from $B$. Then find a cut between these two vertices.
It may not be true, for example, the cut between s and t in the new graph(graph obtained by doing your operation) may be equal to A, then we cannot see anything. I am not sure whether they are equivalent
The definition you gave does not exclude the case $S=A$.
@ Max Alekseyev Thank you, see the detailed explanation in the main text.