# What is a minimum vertex separator as in this definition?

In a research paper the following definition appears that I'm not able to understand completely.

Let $G=(V,E)$ be an undirected unweighted graph with vertex set $V$ and edge set $E$, no self-loops, no parallel-edges. Let $\{ u, v\} \in \binom{V}{2}$ be a vertex pair over the set of all vertices pairs. Let $\textrm{Sep}(u, v)$ be a minimum $u-v$ vertex separator in $G$ if $\{u, v\} \notin E$ or in $G' = (V,E \setminus \{u,v\})$ otherwise.

It is difficult for me to figure out what this definition imply.

In particular can $\textrm{Sep}(u,v)$ be an empty set?

It seems that $Sep(u, v)$ is a vertex separator extended to graphs where $u$ and $v$ are adjacent, by ignoring their common edge.

I assume the correct definition is

... vertex separator in $G$ if $\{u,v\} \notin E$ or in $G′=(V,E \setminus \{\{u,v\}\})$ otherwise.

As given, the definition makes no sense. There is no point in removing $\{u, v\}$ from $E$ if $\{u, v\} \notin E$ and, of course, $\{u, v\} \not\subset E$.

In this case, $Sep(u, v)$ can be $\emptyset$ if $\{u, v\}$ is the only edge connecting two components, or if the graph had two components to begin with.

• Yes, you are right, I've changed the definition, but again I'm not sure this make sense when considering two vertices that already form a bridge for two components. – linello Jul 24 '14 at 16:14
• The usual vertex separator is not defined for adjacent vertices. The paper seems to want to extend that definition. The only other sensible extension seems to be $\{u, v\} \in E \implies Sep(u, v) = \emptyset$, but it doesn't look like they use that one. I wonder, is the paper freely available somewhere, to see what the context is? – Karolis Juodelė Jul 24 '14 at 16:41
• Graph clustering with surprise, complexity and exact solutions. arxiv.org/abs/1310.6019 eq 4 page 8. That constraint means that if nodes $i$ and $j$ are in the same module and nodes $i$ and $k$ are in the same module, then nodes $j$ and $k$ are in the same module. In my opinion constraint (4) could be changed with: $\chi_{ij}+\chi_{jk}-\chi_{ik} \leq 1$ and $\chi_{ij}-\chi_{jk}+\chi_{ik} \leq 1$ and $-\chi_{ij}+\chi_{jk}+\chi_{ik} \leq 1$ with $1\leq i < j < k \leq n$ where $n$ is the number of nodes. Those constraints enforce transitivity of "being in a cluster"-ness. – linello Jul 24 '14 at 19:07
• It seems that (4) could just take $w \in V$. Taking $w \in Sep(u, v)$ is an optimization. A paragraph at the top of page 9 briefly explains why $Sep(u, v)$ is enough and directs to  for full proof. – Karolis Juodelė Jul 24 '14 at 20:12