Algorithms for computing the minimal vertex separator of a graph Background: Let $u,v$ be two vertices of an undirected graph $G=(V,E)$. A vertex set $S\subseteq V$ is a $u,v$-separator if $u$ and $v$ belong to different connected components of $G−S$. If no proper subset of a $u,v$-separator $S$ is a $u,v$-separator then S is a minimal u,v-separator. A vertex set $S \subseteq V$ is a (minimal) separator if there exist vertices $u,v$ such that $S$ is a (minimal) u,v-separator.

Is there some algorithm to compute the minimal vertex separator on a generic graph?

If I'm not interested in the smallest set but just in a set of separator vertices that disconnects $u$ from $v$ how can I do it?
A simple way to find just some minimal $u$-$v$-separator is to find one that is close to $u$. A separator $S$ is called close to $u$ if $S \subseteq N_G(u)$. This is actually very easy and can be done in time $O(n + m)$. Consider the graph $G - N_G(u)$ where $u$ is isolated and $v$ lies in some different component, $C$, which simply contains all vertices which are reachable from $v$. Now, adding the vertices $N_G(u)$ back to the graph, the neighbors $N_G(C)$ of $C$ form a minimal $u$-$v$-separator.

Suppose this was not the case, then there exists $x \in N_G(C)$ such that $N_G(C) \setminus \{x\}$ still separates $u$ and $v$. As $x$ is a neighbor of $u$ and also a neighbor of some vertex in $C$, there exists a path from $u$ through $x$ to $C$, from which $v$ can be reached, a contradiction.

To find $N_G(C)$ in linear time, we can first traverse the neighborhood of $u$ and mark all of its neighbors with some color, say blue. This takes time $O(n)$. Then, we start a DFS at $v$ and mark all reachable vertices with another color, say red. However, when a blue vertex is encountered, it is not visited but simply added to another set, $S$. In the end, $S$ contains all neighbors of $C$. The running time of a DFS is $O(n + m)$, including the time that is needed for checking whether a vertex is blue, and adding it to $S$.

Also, in general any set $S \subseteq V(G)$ which separates $u$ and $v$ can be made minimal in time $O(nm)$ by the following steps:
for each $x \in S$, test whether $S \setminus \{x\}$ still separates $u$ and $v$. If it does, remove $x$ from $S$ and repeat this step. As $S$ can contain at most $n - 2$ vertices and checking whether $u$ and $v$ are still separated can be done by a simple DFS in time $O(m)$, the total time needed is $O(nm)$.