0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – linello
    Jul 24, 2014 at 16:14
  • $\begingroup$ 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? $\endgroup$
    – Karolis Juodelė
    Jul 24, 2014 at 16:41
  • $\begingroup$ 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. $\endgroup$
    – linello
    Jul 24, 2014 at 19:07
  • $\begingroup$ 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. $\endgroup$
    – Karolis Juodelė
    Jul 24, 2014 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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