The width of a hypergraph

Question

In this paper, the width of a hypergraph $H$ is defined as the minimum integer $t$ for which there exists a subset $T$ of $t$ hyperedges in $H$, such that every hyperedge of $H$ intersects at least one hyperedge of $T$.
To better understand this notion, I am trying to relate it to terms related to graphs. I found many "width" terms related to graphs, such as: tree-width, path-width, branch-width and bandwidth. But I could not understand which of these terms, if any, is equivalent to the above definition. Is this "width of a hypergraph" a well-known term in graph theory? Does it have a counterpart for simple graphs, maybe in another name?

Brandon du Preez · Accepted Answer

The exact analogue of this width for simple graphs, where your 'hyperedges' are all normal edges between two vertices, is the 'minimum size of a maximal matching'.
wikipedia - matching
Hyper-edges can be 'large' as subsets of the vertex set, where as edges are quite constrained. So the most 'spiritually similar' concept to this width that is well studied is probably the 'vertex cover number'. This is the size of the smallest subset of vertices that is incident with every edge of the graph.
wikipedia - vertex cover

The width of a hypergraph

One Answer

Add your own answers!

Ask a Question