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

Question

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!

Answer 1

To start with possible NP-hardness (where for each problem, we want a matching/independent set of size at least $k$):

• Independent set is NP-hard on "normal" graphs (and also on hypergraphs)

• Maximum matching is polynomial-time solvable on "normal" graphs, see the wikipedia page on matching.

• Maximum matching is NP-hard in hypergraphs (as shown in this wikipedia page, it is even hard for hypergraphs where each edge contains only 3 vertices).

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^*$.

(If you need further explanation or if this is not your definition of equivalance, please clarify)