1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – R B Feb 26 '14 at 12:55
  • $\begingroup$ 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 $\endgroup$ – vzn Feb 26 '14 at 16:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Apr 28 '14 at 3:59
1
$\begingroup$

heres an example

(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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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