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!

  • $\begingroup$ 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. $\endgroup$ – 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)

  • $\begingroup$ 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. $\endgroup$ – Guess601 Aug 18 '20 at 15:33
  • $\begingroup$ 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? $\endgroup$ – Guess601 Aug 18 '20 at 15:53
  • 1
    $\begingroup$ @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. $\endgroup$ – user53923 Aug 19 '20 at 9:29
  • $\begingroup$ Can you elaborate on the second point please? How can I do NP-hardness reduction when it's not 3-partite? $\endgroup$ – Guess601 Aug 19 '20 at 15:56
  • 1
    $\begingroup$ @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) $\endgroup$ – user53923 Aug 20 '20 at 11:05

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.