3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Adam Smith Feb 12 '15 at 15:09
  • $\begingroup$ @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. $\endgroup$ – Saeed Feb 12 '15 at 17:20
  • $\begingroup$ Right, I read the question too quickly. $\endgroup$ – Adam Smith Feb 13 '15 at 3:47
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think the point is that finding N(C) in a reasonable time is not that trivial. $\endgroup$ – Saeed Feb 12 '15 at 18:15
  • $\begingroup$ It can be done with a simple depth-first search, which just takes linear time. $\endgroup$ – Tobi Feb 12 '15 at 18:19
  • $\begingroup$ 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). $\endgroup$ – Saeed Feb 12 '15 at 18:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Tobi Feb 12 '15 at 18:50
  • $\begingroup$ yes exactly, so I think it's better to include your comment in your answer. $\endgroup$ – Saeed Feb 12 '15 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.