2
$\begingroup$

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!

$\endgroup$
  • $\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$ – C Komus Feb 7 '17 at 10:20
3
$\begingroup$

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)

$\endgroup$

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.