<p>heres an example</p>

<ul>
<li><a href="http://www.sandia.gov/~apinar/papers/NIG.pdf" rel="nofollow">PARTITIONING HYPERGRAPHS IN SCIENTIFIC COMPUTING
APPLICATIONS THROUGH VERTEX SEPARATORS ON GRAPHS</a> KAYAASLAN et al</li>
</ul>

<p>(there is also some research on hypergraph edge separators used in SAT solvers &amp; other edge separators but not incl it because you asked for vertex separators although there is possibly/presumably some connection.)</p>

CC BY-SA 3.0
2014-02-26T16:36:30.607Z
2014-02-26T16:36:30.607Z
vzn
<p>Numerous parameters are defined and considered in the graph theory. I am interested in analogy of these parameters in theory of hypergraphs.</p>

<p>Is there some survey or book or lecture notes about various hypergraph parameters such as independent set, matching, separator, cut, and so on?</p>

<p>In particular, I am interested in an analogy of separator. For a graph $G=(V,E)$, a separator $S$ is a subset of vertices such that removing all elements in $S$ we can obtain two or more separated components $G_{1},G_{2},...$. I am interested in minimum size of separator for hypergraphs.</p>

CC BY-SA 3.0
2014-02-26T12:55:02.680Z
I'm not sure what you are asking here.
Are you interested in finding something you can't define?

What's the motivation of finding this separator in hyper-graphs?
R B
CC BY-SA 3.0
2014-02-26T16:11:58.697Z
there is a research program to find graph analogies in hypergraphs, still at initial stages & largely still open in various ways. see eg [hypergraph decompositions](http://cstheory.stackexchange.com/questions/16220/hypergraph-decompositions-used-in-tcs) tcs.se or [hypergraph decomposition](http://math.stackexchange.com/questions/676550/looking-for-hypergraph-decompositions) math.se
vzn
CC BY-SA 3.0
2014-04-28T03:59:56.270Z
It is common reduce edge-cuts/separators in a hypergraph $G=(V,\mathcal{E})$ to vertex cuts/separators by representing $G$ as a bipartite graph with $V$ one side and $\mathcal{E}$ on the other side. This allows vertex-separator based algorithms to be translated into edge-separator algorithms in hypergraphs. @vzn's reference in his answer is one such example and there are other such papers. I have not seen vertex separators in hyper-graphs. It is not clear that whether there is a useful and suitable definition.
Chandra Chekuri
<reference-request><graph-theory><co.combinatorics><set-system>
Is there an analogy of a vertex separator for hypergraphs?
terne
# Is there an analogy of a vertex separator for hypergraphs?

(Asked by: username_0 on 2014-02-26)

Numerous parameters are defined and considered in the graph theory. I am interested in analogy of these parameters in theory of hypergraphs.

Is there some survey or book or lecture notes about various hypergraph parameters such as independent set, matching, separator, cut, and so on?

In particular, I am interested in an analogy of separator. For a graph $G=(V,E)$, a separator $S$ is a subset of vertices such that removing all elements in $S$ we can obtain two or more separated components $G\_{1},G\_{2},...$. I am interested in minimum size of separator for hypergraphs.

**Tags:** reference-request, graph-theory, co.combinatorics, set-system

> **Comments:**
> **username_1**: I'm not sure what you are asking here. Are you interested in finding something you can't define?  What's the motivation of finding this separator in hyper-graphs?  
> **username_2**: there is a research program to find graph analogies in hypergraphs, still at initial stages & largely still open in various ways. see eg [hypergraph decompositions](http://cstheory.stackexchange.com/questions/16220/hypergraph-decompositions-used-in-tcs) tcs.se or [hypergraph decomposition](http://math.stackexchange.com/questions/676550/looking-for-hypergraph-decompositions) math.se  
> **username_3**: It is common reduce edge-cuts/separators in a hypergraph $G=(V,\mathcal{E})$ to vertex cuts/separators by representing $G$ as a bipartite graph with $V$ one side and $\mathcal{E}$ on the other side. This allows vertex-separator based algorithms to be translated into edge-separator algorithms in hypergraphs. @username_2's reference in his answer is one such example and there are other such papers. I have not seen vertex separators in hyper-graphs. It is not clear that whether there is a useful and suitable definition.  

---

## 1 answers

### Answer by username_2 on 2014-02-26. Score: 1

heres an example

* [PARTITIONING HYPERGRAPHS IN SCIENTIFIC COMPUTING
  APPLICATIONS THROUGH VERTEX SEPARATORS ON GRAPHS](http://www.sandia.gov/~apinar/papers/NIG.pdf) KAYAASLAN et al

(there is also some research on hypergraph edge separators used in SAT solvers & other edge separators but not incl it because you asked for vertex separators although there is possibly/presumably some connection.)


---

