Revision history [back]

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 the graph, 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.

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.

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 the graph, $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.

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.

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.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.

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.

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 size in the following picture, and assume that $A={a,b}\$ and $B={c,d}$. $A={a,b}$ and $B={c,d}$.

Then we can check that $x,y,z$ is the minimum (A, B)-vertex separator. If Simply add a new vertex s connected to all vertices from A, and a vertex t 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.

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 size in the following picture, and assume that $A={a,b}$ and $B={c,d}$.A={a,b} and B={c,d}.

Then we can check that $x,y,z$ is the minimum (A, B)-vertex separator. If 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.

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 size 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 Simply 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.

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 size 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.

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$ $\left{ x, y, z \right}$ 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.

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 $\left{ $\{ x, y, z \right}$ \}$ 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.

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}.$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.

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$ $\{a,b\}$ or $c,d$, $\{c,d\}$, but that's not what we want.