2 added 7 characters in body edited Feb 7 '17 at 9:19 user53923 42322 silver badges66 bronze badges 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 answered Feb 6 '17 at 14:03 user53923 42322 silver badges66 bronze badges 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)