# Is there an analogy of a vertex separator for hypergraphs?

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.

• 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 Feb 26 '14 at 12:55
• 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 tcs.se or hypergraph decomposition math.se – vzn Feb 26 '14 at 16:11
• 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 Apr 28 '14 at 3:59