<p>A simple way to find just <em>some</em> minimal $u$-$v$-separator is to find one that is <em>close</em> to $u$. A separator $S$ is called <em>close</em> 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.</p>

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

<p>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$.</p>

<p>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)$.</p>

CC BY-SA 3.0
2015-02-12T18:15:43.567Z
I think the point is that finding N(C) in a reasonable time is not that trivial.
Saeed
CC BY-SA 3.0
2015-02-12T18:19:47.800Z
It can be done with a simple depth-first search, which just takes linear time.
Tobi
CC BY-SA 3.0
2015-02-12T18:33:40.300Z
it can be done in O(n+E) and it's not hard but either I mistaken or I cannot see how simple we can do this. (we have to change dfs a little bit so I cannot see how simple dfs works).
Saeed
CC BY-SA 3.0
2015-02-12T18:50:45.000Z
Yes, you are right that DFS alone does not work. To find $C$ we can start a DFS at $v$, ignore all vertices of $N(u)$, and mark all vertices that are visited. If $w \in N(u)$ has a neighbor that is marked, then $w$ must be part of the minimal separator. This can be checked in $O(n + m)$ time.
Tobi
CC BY-SA 3.0
2015-02-12T19:00:51.930Z
yes exactly, so I think it's better to include your comment in your answer.
Saeed
CC BY-SA 3.0
2015-02-12T17:44:21.570Z
2015-02-12T22:40:54.783Z
2015-02-12T22:40:54.783Z
Tobi
<p><strong>Background</strong>: 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.</p>

<p>Is there some algorithm to compute the minimal vertex separator on a generic graph?</p>

<p>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?</p>

CC BY-SA 3.0
2015-02-12T15:09:59.487Z
As you have formulated it, this is an exercise in several algorithms textbooks. As such, I'm not sure it is a good fit for this forum. See for example the Kleinberg-Tardos book's chapter on flow algorithms. Are you familiar with algorithms for computing minimum edge cuts?
Adam Smith
CC BY-SA 3.0
2015-02-12T17:20:12.900Z
@AdamSmith op asked for minimal vertex cut not minimum vertex cut, so while flow algorithms can find those minimum vertex cut and they are surely minimal, it doesn't mean it's optimal solution (w.r.t run time). Anyhow the problem is not so hard and maybe it's better to be asked somewhere else, but certainly not that usual homework.
Saeed
CC BY-SA 3.0
2015-02-13T03:47:05.557Z
Right, I read the question too quickly.
Adam Smith
<graph-theory><graph-algorithms><approximation-algorithms>
Algorithms for computing the minimal vertex separator of a graph
linello
# Algorithms for computing the minimal vertex separator of a graph

(Asked by: username_0 on 2015-02-12)

**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?

**Tags:** graph-theory, graph-algorithms, approximation-algorithms
> **Comments:**
> **username_1**: As you have formulated it, this is an exercise in several algorithms textbooks. As such, I'm not sure it is a good fit for this forum. See for example the Kleinberg-Tardos book's chapter on flow algorithms. Are you familiar with algorithms for computing minimum edge cuts?  
> **username_2**: @AdamSmith op asked for minimal vertex cut not minimum vertex cut, so while flow algorithms can find those minimum vertex cut and they are surely minimal, it doesn't mean it's optimal solution (w.r.t run time). Anyhow the problem is not so hard and maybe it's better to be asked somewhere else, but certainly not that usual homework.  
> **username_1**: Right, I read the question too quickly.  

---

## 1 answers

### Answer by username_3 on 2015-02-12. Score: 3

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

> **Comments:**
> **username_2**: I think the point is that finding N(C) in a reasonable time is not that trivial.  
> **username_3**: It can be done with a simple depth-first search, which just takes linear time.  
> **username_2**: it can be done in O(n+E) and it's not hard but either I mistaken or I cannot see how simple we can do this. (we have to change dfs a little bit so I cannot see how simple dfs works).  
> **username_3**: Yes, you are right that DFS alone does not work. To find $C$ we can start a DFS at $v$, ignore all vertices of $N(u)$, and mark all vertices that are visited. If $w \in N(u)$ has a neighbor that is marked, then $w$ must be part of the minimal separator. This can be checked in $O(n + m)$ time.  
> **username_2**: yes exactly, so I think it's better to include your comment in your answer.  

---

