# Is maximum matching problem equivalent to maximum independent set problem in its dual graph?

A hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$.

A subset $M \subseteq E(H)$ is a matching if every pair of edges from $M$ has an empty intersection.

The dual $H^*$ of $H$ is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by $\{e_1, e_2, \cdots , e_m\}$ and whose edges are given by $X = \{X_1, X_2, \cdots, X_n\}$ where $X_j = \{e_i | v_j \in e_i \}$, that is $X_j$ is the collection of all edges containing $v_j$.

My question: Is maximum matching problem equivalent to maximum independent set problem in its dual graph? Are both NP-hard and cannot be approximated to a constant factor in polynomial time (unless P = NP)?

Thank you!

• I find the mix of hypergraph and graph in the question a bit confusing. The maximum matching problem in hypergraphs is known as Set Packing. – C Komus Feb 7 '17 at 10:20

To start with possible NP-hardness (where for each problem, we want a matching/independent set of size at least $k$):
I believe both problems are equivalent in the following sense: set $S \subseteq E(H)$ is a matching in $H$, if and only if $S$ forms an independent set in $H^*$.