2 added 7 characters in body
source | link

To start with possible NP-hardness (where for each problem, we want a matching/independent set of size at least k$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 of edges from E(H)$S \subseteq E(H)$ is a matching in H$H$, if and only if S$S$ forms an independent set in H*$H^*$.

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

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 of edges from 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)

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)

1
source | link

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 of edges from 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)