<p>It seems that $Sep(u, v)$ is a <a href="http://en.wikipedia.org/wiki/Vertex_separator" rel="nofollow">vertex separator</a> extended to graphs where $u$ and $v$ are adjacent, by ignoring their common edge.</p>

<p>I assume the correct definition is  </p>

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

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

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

CC BY-SA 3.0
2014-07-24T16:14:56.113Z
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
CC BY-SA 3.0
2014-07-24T16:41:28.090Z
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ė
CC BY-SA 3.0
2014-07-24T19:07:39.670Z
Graph clustering with surprise, complexity and exact solutions.
http://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
CC BY-SA 3.0
2014-07-24T20:12:53.987Z
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 [6] for full proof.
Karolis Juodelė
CC BY-SA 3.0
2014-07-24T15:38:36.440Z
2014-07-24T15:38:36.440Z
Karolis Juodelė
<p>In a research paper the following definition appears that I'm not able to understand completely.</p>

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

<p>It is difficult for me to figure out what this definition imply.</p>

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

<graph-theory><clustering><partition-problem>
What is a minimum vertex separator as in this definition?
linello
# What is a minimum vertex separator as in this definition?

(Asked by: username_0 on 2014-07-24)

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?

**Tags:** graph-theory, clustering, partition-problem

---

## 1 answers

### Answer by username_1 on 2014-07-24. Score: 3 | Accepted answer

It seems that $Sep(u, v)$ is a [vertex separator](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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?  
> **username_0**: Graph clustering with surprise, complexity and exact solutions. http://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.  
> **username_1**: 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 [6] for full proof.  

---

