# 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. – Christian Komusiewicz 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$):

• 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)

• You wrote "Maximum matching is NP-hard in hypergraphs" according to the wiki page that you referred to. But the wiki page has hypergraphs that are 3-partite. Is maximum matching NP-hard in hypergraphs that are not partite? please give me a reference if you can. – Guess601 Aug 18 at 15:33
• I think it's because it's a special case of the maximum set packing problem where the cardinalities of the sets are not equal. right? – Guess601 Aug 18 at 15:53
• @Guess601 If the problem (Maximum matching in hypergraphs) is NP-hard for some "restricted set" of all possible inputs (3-partite hypergraphs, as shown by the wikipedia), then it is easy to observe (consider the definition of NP-hard) that it is also NP-hard in general (on hypergraphs that may or may not be tripartite). Whether it is NP-hard on jypergraphs that you require NOT to be 3-partite: I assume so, this should be easy to prove, but needs an NP-hardness reduction. – user53923 Aug 19 at 9:29
• Can you elaborate on the second point please? How can I do NP-hardness reduction when it's not 3-partite? – Guess601 Aug 19 at 15:56
• @Guess601 I am not sure I understand why you would want this? Anyways, proving that Maximum matching in non-3-partite hypergraphs is NP-hard could be done by a reduction from Maximum matching in 3-partite hypergraphs (which we know to be NP-hard). If G is an instance for max matching in 3-partite hypergraphs, one can trivially add some hypergraph H to G that is not 3-partite. Then G and H combined are an instance of max matching in non-3partite hypergraphs. (Adjust the size of the matching you are looking for depending on H) – user53923 Aug 20 at 11:05